leetcode错题总结

提交结果：

题目二：

两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/

 这是一道中等难度的题，给出一个单链表，要求交换相邻的节点，例如第一个节点和第二个节点交换，第三个节点和第四个节点交换。并且要求不能只更换值，要整个节点一起更换。

首先想到的是双栈。思想：先创建两个栈用于存储节点，再遍历一遍链表，相邻的节点分别分开存储于两个栈中，再重新从栈顶取出节点，改变他们的指向关系。

这是我第一次提交的代码：

class Solution {public ListNode swapPairs(ListNode head) {ListNode cur=head;int flag=0;if (head==null) return null;Stack stack1 = new Stack<>();Stack stack2 = new Stack<>();while (cur!=null){if (flag%2==0){stack1.push(cur);}else {stack2.push(cur);}flag++;cur=cur.next;}//这里判断是否总共有奇数个节点，若有奇数个节点则最后一个节点不用更换，则保留原来的指向关系//否则将倒数第二个节点（即stack1的栈顶节点）的next设置为空，因为更换后他就是最后一个节点if (stack1.size()>stack2.size()){ListNode node = stack1.pop();stack1.peek().next=node;}else {stack1.peek().next=null;}while (!stack1.isEmpty()){stack2.peek().next=stack1.pop();stack1.peek().next=stack2.pop();}return stack2.peek();}
}

然而这里报了空栈异常。后来检查发现，当循环到每个栈中只有最后一个节点的时候，此时stack2的栈顶节点的next指向stack1时，顺便把stack1的栈顶节点移出，此时再执行

stack1.peek().next=stack2.pop();

这句代码的时候，stack1已经为空。

其实satck1为空时，已经没有必要执行这句代码了，因为此时stack2的最后一个节点作为新链表的头节点已经指向了head了。所以只需要在这代码前面加上一个判断条件判断stack1是否为空就可以提交成功了。

修改后的代码：

class Solution {public ListNode swapPairs(ListNode head) {ListNode cur=head;int flag=0;if (head==null||head.next==null) return head;Stack stack1 = new Stack<>();Stack stack2 = new Stack<>();while (cur!=null){if (flag%2==0){stack1.push(cur);}else {stack2.push(cur);}flag++;cur=cur.next;}if (stack1.size()>stack2.size()){ListNode node = stack1.pop();stack1.peek().next=node;}else {stack1.peek().next=null;}while (!stack1.isEmpty()){stack2.peek().next=stack1.pop();if (stack1.size()!=0){stack1.peek().next=stack2.pop();}}return stack2.peek();}
}

提交结果：

 这里时间击败了100哈哈，使用双栈损耗了内存确实换来了很好的时间性能，而且这里空间也击败了88还不错。最后其实还可以优化一下，这里的cur属实是有点多余了，因为最后返回结果不用head标记的节点，所以这里完全可以用head去遍历并入栈，所以这里的空间还可以再优化一下。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！