两两交换链表中的节点(Swap Nodes in Pairs)

2019年5月25日

 

题目描述:

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

    给定 1->2->3->4, 你应该返回 2->1->4->3.

链表类:

class ListNode{

int val;

ListNode next;

ListNode(int x){ val = x; }

}

解题思路:

注意:在进行交换时:要保证链表的各个部分的引用均不被丢弃.

 

          (一般情况)

情况一(绿色线段表示):当两两交换的链表处于链表的第一和第二位置

步骤一:保存奇数节点(节点3)的引用;

步骤二:保存偶数节点(节点4)的引用;

是步骤四的前提,如果不保存,步骤三过后节点4的引用将被丢弃.

(步骤三和步骤四不可调换,否则需要额外的内存(引用)来保存节点5的引用信息)

步骤三:节点3.next=节点5;

步骤四:节点4.next=节点3;

 

 

          (特殊情况)

情况二(黑色线段表示):当两两交换的链表不是处于链表的第一和第二位置

步骤一:保存奇数节点(节点1)的引用;

步骤二:保存偶数节点(节点2)的引用;

与情况一不同的是:保存偶数节点的引用为交换后链表的头引用,而不能是情况一的中间变量,否则中间变量在进行下一重循环而重新赋值后,交换后的链表头的引用将被丢弃.

(步骤三和步骤四不可调换,否则需要额外的内存(引用)来保存节点3的引用信息)

步骤三:节点1.next=节点3;

步骤四:节点2.next=节点1;

具体代码1:

public ListNode swapPairs(ListNode head) { // 非空验证 if(head == null || head.next == null){ return head; } // 交换结果链表头引用 ListNode reverse = head; // 当前交换位置 ListNode current = head; // 两两交换的前一链表的引用(使已交换的链表指向刚交换好的链表节点) ListNode forSwap = null; while(current != null){ // 如果总链表的节点数为奇数,则最后那个节点就没必要进行交换 if(current.next != null){ /********步骤一********/ ListNode odd = current; /********步骤二********/ // 情况一 if(forSwap != null){ forSwap.next = odd.next; } // 情况二 if(current == head){ reverse = odd.next; } /********步骤三********/ odd.next = odd.next.next; /********步骤四********/ if(forSwap != null) { // 情况一 forSwap.next.next = odd; }else{ // 情况二 reverse.next = odd; } // 更新要交换的下两个节点信息 current = odd.next; forSwap = odd; }else { return reverse; } } return reverse; }

在LeetCode运行的结果:

成功

显示详情 

执行用时 : 1 ms, 在Swap Nodes in Pairs的Java提交中击败了94.04% 的用户

内存消耗 : 34.1 MB, 在Swap Nodes in Pairs的Java提交中击败了88.92% 的用户

来自 <https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/>

 

具体代码2:

(思路和代码1相同,只不过两两交换的第二个节点用了额外的变量进行保存,但运行情况却比较代码1好一点,我不明白的是明明引用少了一个,为什么内存消耗为什么反而减小?初学算法,请多多指教)

public ListNode swapPairs(ListNode head) { // 非空验证 if(head == null || head.next == null){ return head; } ListNode reverse = head; ListNode current = head; ListNode forSwap = null; while(current != null){ if(current.next != null){ /********步骤一********/ ListNode odd = current; /********步骤二********/ ListNode even = odd.next; if(current == head){ reverse = even; } /********步骤三********/ odd.next = even.next; /********步骤四********/ even.next = odd; // 链接到已交换的链表后 if(forSwap != null){ forSwap.next = even; } current = odd.next; forSwap = odd; }else { return reverse; } } return reverse; }

在LeetCode运行的结果:

成功

显示详情 

执行用时 : 1 ms, 在Swap Nodes in Pairs的Java提交中击败了94.04% 的用户

内存消耗 : 33.9 MB, 在Swap Nodes in Pairs的Java提交中击败了90.90% 的用户

来自 <https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/>

 

附:不知道LeetCode运行时会不会受到当时服务器的速度影响,还是LeetCode针对提交的代码有一套自己对时间复杂度和空间复杂度有一套自己的算法,总感觉提交后有些许不同.

 邮箱:  lylgjiavg@163.com  声明:  Copyright, 2019            转载请注明出处！