LeetCode--24. Swap Nodes in Pairs

本文主要是介绍LeetCode--24. Swap Nodes in Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://leetcode.com/problems/swap-nodes-in-pairs/

思路类似于逆转单链表（https://blog.csdn.net/To_be_to_thought/article/details/83930978）找出循环不变式，链表题目画画图就出来了。

思路具体如图：

                            

循环不变式提炼如下：

            rear.next=front.next;baseRear.next=front;front.next=rear;baseRear=rear;front=rear.next;rear=front.next;

代码如下：

class Solution {public ListNode swapPairs(ListNode head) {ListNode virtual=new ListNode(0);virtual.next=head;if(head==null || head.next==null)return head;ListNode baseRear=virtual;ListNode rear=head;ListNode front=head.next;while(front.next!=null && front.next.next!=null){rear.next=front.next;baseRear.next=front;front.next=rear;baseRear=rear;front=rear.next;rear=front.next;}rear.next=front.next;baseRear.next=front;front.next=rear;return virtual.next;}
}

但是运行“Time Limited Exceed”，不是只有空间复杂度限制吗？这题是送分题呀，怎么？？？真是一顿操作猛如虎，啪啪打脸！！！

原来循环不变式代码有小错误：

                                                      

应该改为：

                                                      

还可以更简洁些！！！

class Solution {public ListNode swapPairs(ListNode head) {ListNode virtual=new ListNode(0);virtual.next=head;if(head==null || head.next==null)return head;ListNode baseRear=virtual;while(baseRear.next!=null && baseRear.next.next!=null){ListNode rear=baseRear.next;ListNode front=rear.next;rear.next=front.next;baseRear.next=front;front.next=rear;baseRear=rear;}return virtual.next;}
}

在Discussion中看到一种代码十分简洁的递归解法，这个解法真妖孽！！！：

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null)return head;ListNode prev = null;ListNode curr = head;ListNode next = head.next;ListNode newHead = next;curr.next = swapPairs(next.next);next.next = curr;return newHead;}
}

但他妈递归的栈空间不是O(n)吗？

这篇关于LeetCode--24. Swap Nodes in Pairs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---