「力扣」 第 24 题：两两交换链表中的结点

递归 单链表
专题 6：链表
发布日期:   2017-08-05

「力扣」 第 24 题：两两交换链表中的结点

英文网址：24. Swap Nodes in Pairs ；

中文网址：24. 两两交换链表中的节点 。

我写的题解：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/chuan-zhen-yin-xian-di-gui-by-liweiwei1419-2/

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例：

给定 1 -> 2 -> 3 -> 4, 你应该返回 2 -> 1 -> 4 -> 3.

说明:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

穿针引线和递归。

方法一：穿针引线

image-20191129143317788

Java 代码：用 3 个指针

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public ListNode(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("arr can not be empty");
        }
        this.val = nums[0];
        ListNode curr = this;
        for (int i = 1; i < nums.length; i++) {
            curr.next = new ListNode(nums[i]);
            curr = curr.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            s.append(cur.val);
            s.append(" -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}


public class Solution {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 这里设置 dummyNode 是为了处理头结点的特殊情况
        // 使得头结点和非头结点可以统一处理
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode curNode = dummyNode;

        while (curNode.next != null && curNode.next.next != null) {
            // 重新初始化 p1 和 p2
            ListNode p1 = curNode.next;
            ListNode p2 = p1.next;

            // "穿针引线"的步骤就 3 步
            p1.next = p2.next;
            p2.next = p1;
            curNode.next = p2;

            // 循环变量更新
            curNode = p1;
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        // 给定 1->2->3->4, 你应该返回 2->1->4->3.
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode swapPairs = solution.swapPairs(head);
        System.out.println(swapPairs);
    }
}

Java 代码：用 4 个指针

public class Solution {
    public ListNode swapPairs(ListNode head) {
        // 特判
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode curNode = dummyNode;
        ListNode p1;
        ListNode p2;
        ListNode nextNode;
        while (curNode.next != null && curNode.next.next != null) {
            p1 = curNode.next;
            p2 = p1.next;

            // 先保存一下
            nextNode = p2.next;
            // 穿针引线
            curNode.next = p2;
            p2.next = p1;
            p1.next = nextNode;
            // 特别注意，下一轮 curNode 应该站在 p1
            curNode = p1;
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        // 给定 1->2->3->4, 你应该返回 2->1->4->3.
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode swapPairs = solution.swapPairs(head);
        System.out.println(swapPairs);
    }
}

方法二：递归

Java 代码：如果使用递归的方法，就特别简单。

public class Solution2 {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode newHead = swapPairs(p2.next);
        // 下面这两行代码可以交换
        p1.next = newHead;
        p2.next = p1;
        return p2;
    }

}

Java 代码：

public class Solution {

    // 递归处理

    public ListNode swapPairs(ListNode head) {
        // 特判
        if (head == null || head.next == null) {
            return head;
        }

        // 没有必要设置虚拟头结点了
        ListNode p1 = head;
        ListNode p2 = head.next;

        p1.next = swapPairs(p2.next);
        p2.next = p1;
        return p2;
    }
}

Java 代码：

public class Solution {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        p1.next = swapPairs(p2.next);
        p2.next = p1;
        return p2;
    }
}

分析：两种方法：1、用递归来做就特别简单；2、穿针引线比较麻烦。

解法1：穿针引线做法：设计以下 4 个引用（指针）。
1、成对的结点 1 ：node1
2、成对的结点 2 ：node2
3、成对的结点 1 的前驱：p
4、成对的结点 2 的后继：next

Java 代码：

class ListNode {

    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {

    /**
     * 交换链表中成对的元素
     * （自己把图画出来，对于指针交换的过程就好理解了）
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);

        dummyNode.next = head;
        ListNode p = dummyNode;
        while (p.next != null && p.next.next != null) {
            ListNode node1 = p.next;
            ListNode node2 = node1.next;
            ListNode next = node2.next;

            node1.next = next;
            node2.next = node1;
            p.next = node2;
            p = node1;
        }
        return dummyNode.next;
    }


    public ListNode createLinkedList(int[] arr) {
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    public void printLinkedList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.printf("%d => ", current.val);
            current = current.next;
        }
        System.out.println("NULL ");
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        Solution solution = new Solution();
        ListNode head1 = solution.createLinkedList(arr);
        solution.printLinkedList(head1);
        ListNode reverseHead = solution.swapPairs(head1);
        solution.printLinkedList(reverseHead);
    }
}

说明：以下及其以后的动图如果没有特别说明，都来自这个伟大的 GitHub 仓库：https://github.com/MisterBooo/LeetCodeAnimation/blob/master/Readme.md。

解法2：如果使用递归的方法，就特别简单。

Java 代码：

/**
 * @author liwei
 * @date 18/7/4 下午9:42
 */
public class Solution2 {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode newHead = swapPairs(p2.next);
        // 下面这两行代码可以交换
        p1.next = newHead;
        p2.next = p1;
        return p2;
    }

}

下面这样写就更简单了：

Java 代码：

public class Solution4 {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        first.next = swapPairs(second.next);
        second.next = first;
        return second;
    }

    public static void main(String[] args) {
        // 给定 1->2->3->4, 你应该返回 2->1->4->3.
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode swapPairs = solution.swapPairs(head);
        System.out.println(swapPairs);
    }
}

参考资料：https://blog.csdn.net/Koala_Tree/article/details/81476772。

文章作者： liweiwei1419
文章链接： https://liweiwei1419.gitee.io/leetcode-algo/2017/08/05/leetcode-algo/0024-swap-nodes-in-pairs/
版权声明： 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
递归 单链表
赏
评论
 上一篇
「力扣」第 25 题：两个数相加（中等） 「力扣」第 25 题：两个数相加（中等）
「力扣」第 25 题：K 个一组翻转链表（困难） 英文网址：25. Reverse Nodes in k-Group ； 中文网址：25. k个一组翻转链表 。 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一
2017-08-06 专题 6：链表
单链表
下一篇 
「力扣」第 23 题：合并 K 个排序链表（困难） 「力扣」第 23 题：合并 K 个排序链表（困难）
「力扣」第 23 题：合并 K 个排序链表（困难） 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists 我写的题解地址：https://leetcode-cn.com/prob
2017-08-04 专题 6：链表
分治算法 优先队列 单链表 贪心算法
  目录