首页 > 代码库 > LeetCode: Swap Nodes in Pairs 解题报告

LeetCode: Swap Nodes in Pairs 解题报告

2024-08-05 05:32:10   208人阅读

Swap Nodes in Pairs

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

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

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

SOLUTION 1:

递归解法：

1. 先翻转后面的链表，得到新的Next.

2. 翻转当前的2个节点。

3. 返回新的头部。

 1 // Solution 1: the recursion version. 2     public ListNode swapPairs1(ListNode head) { 3         if (head == null) { 4             return null; 5         } 6          7         return rec(head); 8     } 9     10     public ListNode rec(ListNode head) {11         if (head == null || head.next == null) {12             return head;13         }14         15         ListNode next = head.next.next;16         17         // 翻转后面的链表18         next = rec(next);19         20         // store the new head.21         ListNode tmp = head.next;22         23         // reverse the two nodes.24         head.next = next;25         tmp.next = head;26         27         return tmp;28     }
View Code

 

SOLUTION 2:

迭代解法：

1. 使用Dummy node保存头节点前一个节点

2. 记录翻转区域的Pre（上一个节点），记录翻转区域的next，或是tail。

3. 翻转特定区域，并不断前移。

有2种写法，后面一种写法稍微简单一点，记录的是翻转区域的下一个节点。

 

 1 // Solution 2: the iteration version. 2     public ListNode swapPairs(ListNode head) { 3         // 如果小于2个元素，不需要任何操作 4         if (head == null || head.next == null) { 5             return head; 6         } 7          8         ListNode dummy = new ListNode(0); 9         dummy.next = head;10         11         // The node before the reverse area;12         ListNode pre = dummy;13         14         while (pre.next != null && pre.next.next != null) {15             // The last node of the reverse area;16             ListNode tail = pre.next.next;17             18             ListNode tmp = pre.next;19             pre.next = tail;20             21             ListNode next = tail.next;22             tail.next = tmp;23             tmp.next = next;24             25             // move forward the pre node.26             pre = tmp;27         }28         29         return dummy.next;30     }
View Code

 

 1 // Solution 3: the iteration version. 2     public ListNode swapPairs3(ListNode head) { 3         // 如果小于2个元素，不需要任何操作 4         if (head == null || head.next == null) { 5             return head; 6         } 7          8         ListNode dummy = new ListNode(0); 9         dummy.next = head;10         11         // The node before the reverse area;12         ListNode pre = dummy;13         14         while (pre.next != null && pre.next.next != null) {15             ListNode next = pre.next.next.next;16             17             ListNode tmp = pre.next;18             pre.next = pre.next.next;19             pre.next.next = tmp;20             21             tmp.next = next;22                         23             // move forward the pre node.24             pre = tmp;25         }26         27         return dummy.next;28     }
View Code

 

GITHUB:

 

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/list/SwapPairs3.java

LeetCode: Swap Nodes in Pairs 解题报告


联系
我们