24. Swap Nodes in Pairs

题目描述和难度

  • 题目描述：

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

示例:

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

说明:

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

思路分析

求解关键：虽然这道问题被标注为“中等”，但是只要是链表的问题做多了的话，就会知道，解这类链表的问题有两个套路。

  • 1、递归
  • 2、穿针引线

参考解答

参考解答1

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 + " -> ");
            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;
        }
        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);
    }
}

参考解答2

public class Solution2 {

    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) {
            ListNode first = curNode.next;
            ListNode second = first.next;

            ListNode third = second.next;

            // 交换
            second.next = first;
            first.next = third;

            // 和之前 swap 的链表接上
            curNode.next = second;

            // 站在下一轮交换的结点前面
            curNode = first;
        }
        return dummyNode.next;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0024-swap-nodes-in-pairs ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。