leetcode-24. 两两交换链表中的节点

JAVA解法

/**
 * 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 dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        // 交换需要 3 个节点都不能为空
        while (temp.next != null && temp.next.next != null) {
            // temp 节点往右第一个节点
            ListNode node1 = temp.next;
            // temp 节点往右第二个节点
            ListNode node2 = temp.next.next;
            // temp 指向 node2 节点
            temp.next = node2;
            // node1 指向 node3 节点
            node1.next = node2.next;
            // node2 指向 node1 节点
            node2.next = node1;
            // 把之前的 node1 节点赋值给 temp 节点
            temp = node1;
        }
        // 返回交换后的链表
        return dummyHead.next;
    }
}

题解分析

首先要给链表加上一个中间节点 temp 在头节点之前，定义 node1 为 temp 之后的原先的 head 节点，node2 为 head 的下一个节点。

需要 3 个节点都不能为空才能进入循环，让 temp 指向 node2 节点，node1 指向 node3 节点，node2 指向 node1 节点，这样；便可把相邻的两个节点进行交换。

由于上面已经完成了交换，此时的 node1 在未进行交换前的 node2 的位置处。把之前的 node1 节点赋值给 temp 节点，此时的 temp 跳过原来的 node2 节点来到了 原来 node1 节点处，为整个链表的第三个节点。

再进行循环，此时的 temp.next 是第三个节点，temp.next.next 为第四个节点，再次交换，temp 不受影响，以此类推，最后把 head 返回，即返回 dummyHead.next 即可。

leetcode原题： 24. 两两交换链表中的节点