题目描述: 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 链表类: class ListNode{ intval; ListNodenext; ListNode(intx){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/>邮箱: lylgjiavg@163.com Copyright, 2019 转载请注明出处！
