Leetcode24-两两交换链表中的节点详解_链表的排序两两交换是什么原理

往期博客：

Leetcode1-两数之和详解

Leetcode2-两数相加代码详解

Leetcode20-有效的括号详解

Leetcode21-合并两个有序链表详解

Leetcode22-有效括号生成详解

---

目录

题目

示例

解析

迭代法

代码

Python代码

Java代码

迭代法

代码

Python代码

Java代码

---

题目

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

让我们分析一下题目：

已知：一个链表

目的：交换相邻两节点

要求：返回交换后的链表头节点

示例

示例1

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

示例2

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

示例3

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

解析

迭代法

对于迭代法就是将链表从头到尾进行遍历，将链表中的相邻两节点进行两两交换了，但是这里要注意的时，在链表中我们变换的链表指针的指向，从而达到变换链表节点顺序的效果。

对于下图示例，将链表1—>2—>3—>1中相邻两节点进行两两交换，首先创建虚拟节点res，并将当前指针cur指向虚拟头结点，head指针指向第一个节点“1”，next指针指向第二个节点“2”，tmp指针指向第三个节点“3”

首先是交换节点“1”和节点“2”的顺序，断开节点“res”与节点“1”的指针，并将指针指向节点“2”

 断开节点“2”与节点“3”的指针，并将节点“2”指向节点“1”

将节点“1”指向节点“3”

至此，已经完成了第一节点和第二节点的交换

再进行第二次迭代，交换第三节点和第四节点，但此时cur指向节点“2”，head指向节点“1”，next指向节点“3”，tmp指第四节点“1”，然后再进行如上操作

 最终得到最后讲过全部交换后的链表

代码

Python代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        
        # 对于空链表只有一个节点的链表，直接返回原链表
        if head == None or head.next == None:
            return head
 
        res = ListNode()  # 创建虚拟头结点
        res.next = head  # head指向第一个节点
        cur = res  # cur指向虚拟节点
 
        while cur.next != None and cur.next.next != None:
            nxt = head.next  # nxt指向第二节点
            tmp = nxt.next  # tmp指向第三节点
            cur.next = nxt  # 虚拟头节点指向第二节点
            nxt.next = head  # 第二节点指向第一节点
            head.next = tmp  # 第一节点指向第三节点
 
            cur = head  # 准备第二次迭代, cur第一节点
            head = head.next  # head指向第二节点
        return res.next  # 返回交换后的链表，即虚拟头结点后的所有节点

Java代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            ListNode next = head.next;
            ListNode tmp = head.next.next;
            cur.next = next;
            next.next = head;
            head.next = tmp;
            cur = head;
            head = head.next;
        }
        return res.next;
 
    }
}

迭代法

将head指向第一节点“1”，将next指向第二节点“2”

将第一节点指向第三节点，同时第三第四节点进行递归，head指向第三节点，next指向第四节点

其中递归部分将第四节点指向第三节点

然后第二几点指向第一节点

 所以最终得到最后所有家电见后顺序后的链表

代码

Python代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        
        # 对于空链表只有一个节点的链表，直接返回原链表
        if head == None or head.next == None:
            return head
 
        nxt = head.next
        head.next = self.swapPairs(head.next.next)
        nxt.next = head
        return nxt

Java代码

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