[LeetCode] 24. Swap Nodes in Pairs

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

You may not modify the values in the list's nodes. Only nodes itself may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints:

The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100

两两交换链表中的节点。给一个linked list，请成对调换node。

我的思路是迭代。依然是给一个dummy节点放在head节点之前，然后dummy.next是head节点，nextStart是第三个节点，需要交换的只是l2和l2.next，l1永远是需要swap的两个节点之前的那个节点，他不参与swap。每次交换完了之后只往前挪动一个节点的距离。我画了一个示意图，这样不容易错。

dummy -> 1 -> 2 -> 3 -> 4

l1 l2 ns

时间O(n)

空间O(1)

JavaScript实现

 1 /**
 2  * @param {ListNode} head
 3  * @return {ListNode}
 4  */
 5 var swapPairs = function(head) {
 6     // corner case
 7     if (head === null || head.next === null) {
 8         return head;
 9     }
10 
11     // normal case
12     let dummy = new ListNode(0);
13     dummy.next = head;
14     let l1 = dummy;
15     let l2 = head;
16     while (l2 !== null && l2.next !== null) {
17         let nextStart = l2.next.next;
18         l1.next = l2.next;
19         l2.next.next = l2;
20         l2.next = nextStart;
21         l1 = l2;
22         l2 = l2.next;
23     }
24     return dummy.next;
25 };

Java实现

 1 class Solution {
 2     public ListNode swapPairs(ListNode head) {
 3         // corner case
 4         if (head == null || head.next == null) {
 5             return head;
 6         }
 7 
 8         // normal case
 9         ListNode dummy = new ListNode(0);
10         dummy.next = head;
11         ListNode l1 = dummy;
12         ListNode l2 = head;
13         while (l2 != null && l2.next != null) {
14             ListNode nextStart = l2.next.next;
15             l1.next = l2.next;
16             l2.next.next = l2;
17             l2.next = nextStart;
18             l1 = l2;
19             l2 = l2.next;
20         }
21         return dummy.next;
22     }
23 }

LeetCode 题目总结