代码随想录笔记_链表_24两两交换链表中的节点

代码随想录二刷笔记记录

LC24.两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

思路：设置一个虚拟节点 dummy. 四个指针 pre,cur,post,nextCur，即可解决本题

例如

输入：head = [1,2,3,4]
输出：[2,1,4,3]
dummy -> 2 -> 1 -> 3
同理 1 -> 4 -> 3
即可两两交换

分析：

完整代码

public ListNode swapPairs(ListNode head) {
    //虚拟头节点
    ListNode dummy = new ListNode(-1,head);
    //pre指向虚拟头节点
    ListNode pre = dummy;
    //cur指向头节点
    ListNode cur = head;
    while (pre.next != null && pre.next.next != null){
    	//post指针，指向cur之后的节点
        ListNode post = cur.next;
        //nextCur为下一个Cur占位
        ListNode nextCur = cur.next.next;
        //dummy -> 2
        pre.next = post;
        //2 -> 1
        post.next = cur;
        //1 -> 3
        cur.next = nextCur;
        //重置pre和cur的位置，准备下一次操作
        pre = cur;
        cur = nextCur;
    }
    return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24