LeetCode_双指针_中等_24.两两交换链表中的节点

我不是女神ヾ 2023-10-09 21:32 49阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**

![在这里插入图片描述][9f653ecc19ac42588486d7e19de228d1.png]

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

**示例 2：**  
输入：head = \[\]  
输出：\[\]

**示例 3：**  
输入：head = \[1\]  
输出：\[1\]

**提示：**  
链表中节点的数目在范围 \[0, 100\] 内  
0 <= Node.val <= 100

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/swap-nodes-in-pairs

## 2.思路 ##

（1）递归

（2）迭代

（3）双指针 & 递归  
本题可以看作[25.K 个一组翻转链表][25.K]这题的特殊情况，即 k = 2 的情况。

思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_双指针\_递归\_困难\_25.K 个一组翻转链表][25.K]  
[LeetCode\_双指针\_递归\_简单\_206.反转链表][LeetCode_206.]

## 3.代码实现（Java） ##

//思路1————递归
    /**
     * 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) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode newHead = head.next;
            head.next = swapPairs(newHead.next);
            newHead.next = head;
            return newHead;
        }
    }

//思路2————迭代
    /**
     * 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(-1, head);
            ListNode p = dummy;
            while (p.next != null && p.next.next != null) {
        
                ListNode node1 = p.next;
                ListNode node2 = p.next.next;
                p.next = node2;
                node1.next = node2.next;
                node2.next = node1;
                p = node1;
            }
            return dummy.next;
        }
    }

//思路3————双指针 & 递归
    /**
     * 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) {
        
            int k = 2;
            return reverseKGroup(head, k);
        }
    
        public ListNode reverseKGroup(ListNode head, int k) {
        
            if (head == null || head.next == null) {
        
                return head;
            }
            ListNode node1 = head;
            ListNode node2 = head;
            for (int i = 0; i < k; i++) {
        
                //待反转的节点总数不足 k 个，无需反转，保留原有顺序即可
                if (node2 == null) {
        
                    return head;
                }
                node2 = node2.next;
            }
            //反转前 k 个元素
            ListNode newHead = reverse(node1, node2);
            //递归反转后续链表并连接起来
            node1.next = reverseKGroup(node2, k);
            return newHead;
        }
        
        //反转链表区间 [node1, node2)
        public ListNode reverse(ListNode node1, ListNode node2) {
        
            ListNode prev = null;
            ListNode curr = node1;
            while (curr != node2) {
        
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            //返回反转后的头节点
            return prev;
        }
    }

[9f653ecc19ac42588486d7e19de228d1.png]: https://img-blog.csdnimg.cn/9f653ecc19ac42588486d7e19de228d1.png
[25.K]: https://blog.csdn.net/weixin_43004044/article/details/122739524
[Link 1]: https://leetcode.cn/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
[LeetCode_206.]: https://blog.csdn.net/weixin_43004044/article/details/124894199