24. 两两交换链表中的节点

题干

24. 两两交换链表中的节点

难度中等478收藏分享切换为英文关注反馈

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

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

示例:

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

思路一（遍历）

• 对于链表操作，需要注意的点

1. 假设有链表x->y, 也就是x.next = y
   但是当你对x.next进行赋值时，其修改的并不是y，而是x的next指针，这样做并不会对y结点产生任何影响，它只是对x结点的后继结点进行更换

   这也是很多新手操作链表存在的误区

2. 每个结点只有一个next，也就是说一旦一个结点的next被修改，其改动之前的next如果不做记录便会断掉

• 比较经典的链表操作题目，主要思路就是使用两个指针分别指向要交换的两个结点，交换之后对指针进行后移

  可以做一个空的头结点fakehead，让头结点指向链表的head，这样便于后续统一操作。

• python 代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        fakeFead = ListNode(None)
        fakeFead.next = head
        pre, after = fakeFead, head.next
        while after is not None:
            pre.next.next = after.next
            after.next = pre.next
            pre.next = after
            if after.next.next is None:
                break
            after = after.next.next.next
            pre = pre.next.next
        return fakeFead.next

思路二（递归）

• 链表本身就是一种递归的数据结构，使用递归处理起来会更容易

  编程的思想就是先假定swapPairs(self, head: ListNode) -> ListNode:函数返回的就是换序后的链表，我们每次递归做的操作只是把相邻两个结点head->res换序，然后把换序之后的后一个节点``head链接到swapPairs(res.next)`函数返回值上，然后整个函数返回换序之后的前一个结点。

• python代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        res=head.next
        head.next=self.swapPairs(res.next)
        res.next=head
        return res