LeetCode 24. 两两交换链表中的节点

题目大意

给定一个单链表，需要将链表中的节点按顺序两两交换，并返回交换后新的链表头节点。禁止只交换节点的数值，必须真实地调整指针。当链表长度为奇数时，最后一个节点保持原状。

示例

  • 输入：head = [1,2,3,4]
  • 输出：[2,1,4,3]

当输入为 head = [1,2,3] 时，结果应为 [2,1,3]，因为第三个节点无法参与交换。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);//初始化 0->1->2->3->4
        ListNode curr = dummy.next;
        ListNode node0 = dummy;
        ListNode node1 = curr;
      
        while (node1 != null && node1.next != null) {//至少为两个节点
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;

            node0.next = node2;//0->2
            node1.next = node3;//1->3
            node2.next = node1;//2->1

            node0 = node1;//交换 在下一次的循环中1就是0
            node1 = node3;//3就是1
        }

        return dummy.next;
    }
}