［抄題］：

?

Given a?linked list, swap every two adjacent nodes and return its head.

?

Example:

?

Given 1->2->3->4, you should return the list as 2->1->4->3.

?

Note:

?

• Your algorithm should use only constant extra space.
• You may?not?modify the values in the list's nodes, only nodes itself may be changed.

?

?[暴力解法]：

時間分析：

空間分析：dummy node，新建才是n，不新建就是1

?[優化后]：

時間分析：

空間分析：recursive用的是stack, 空間恒定為n.

特例：尾遞歸是1

［奇葩輸出條件］：

［奇葩corner case］：

從節點非空就行了

［思維問題］：

不知道指針用什么順序交換：

先外后里，外面的兩點前后無所謂。

［英文數據結構或算法，為什么不用別的數據結構或算法］：

［一句話思路］：

用一個cur做主節點 負責移動，一個first second分別做后面兩個從節點（因此循環條件就是從節點非空？）

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

不知道指針的改變是按什么順序的：先外面、后里面

不知道指針的改變怎么寫：就和方程左邊指向方程右邊即可

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結果]：

［總結］：

學了很多：先外后里，左指右，從節點非空

［復雜度］：Time complexity: O(n) Space complexity: O(1)

［算法思想：迭代/遞歸/分治/貪心］：

［關鍵模板化代碼］：

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

?[代碼風格] ：

?[是否頭一次寫此類driver funcion的代碼] ：

?[潛臺詞] ：

?

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode swapPairs(ListNode head) {//ccif (head == null) return head; //ini: dummy nodeListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;//while loop if the two nodes are not nullwhile (cur.next != null && cur.next.next != null) {//initialize two ListNodeListNode first = cur.next;ListNode second = cur.next.next;//change the pointercur.next = second;first.next = second.next;second.next = first;//move the curcur = cur.next.next;}return dummy.next;} } View Code

?

轉載于:https://www.cnblogs.com/immiao0319/p/9397580.html

總結

以上是生活随笔為你收集整理的24. Swap Nodes in Pairs 链表每2个点翻转一次的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。