24-两两交换链表中的结点

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

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

---

示例

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

---

解法

非递归

• 设立新的头结点H的好处是：使得交换前两个结点时的操作和后面的完全一致，不用分开处理。
• 指针pre和p：分别指向要交换的两个结点，每次向后移动两个结点
• 指针rear：指向已经排好顺序的部分的尾端，初始指向头结点
• 结束条件：p指向位置为空

# 非递归解法
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head==None or head.next==None:
            return head
        # 创建一个不含任何信息的头结点，并添加到原链表的前面
        H = ListNode(None)
        H.next = head
        rear =H #指向已完成交换部分的尾结点，初始为头结点H
        pre,p = head,head.next #分别指向要交换的两个结点
        while p:
            # 重新调整结点位置
            pre.next = p.next
            p.next = pre
            rear.next = p
            # 更新指针
            rear = pre
            pre = pre.next
            p = pre.next if pre else None
        return H.next

递归法

# 递归解法
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 结点数为0或1时
        if head == None or head.next == None:
            return head
        # 每次处理两个结点，head和N
        N = head.next
        # head处理后变为后面的结点，
        # 需要和后面递归的首元素连接起来
        head.next = self.swapPairs(N.next)
        # 原来后面的元素放到前面
        N.next = head
        # 最后返回的是N（后面的变到了前面）
        return N

---

来源

LeetCode中该题地址，Click here!