【链表】leetcode每日一题—24.两两交换链表中的结点_给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改

题目：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路一：递归

解答一：递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路二：非递归

• 此处为了统一操作，引入了虚拟头节点。
• 指针的变化过程如①②③所示，需要注意：
  如果某个节点的next指向发生变化，则其下一个节点需要被记录。该题中所需要记录的节点如图tmp1和tmp2所示。
• 下次将cur调整到1的位置，即待交换节点（3和4）前面的节点。
  

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre=ListNode()
        pre.next=head
        cur=pre
        while cur.next and cur.next.next:
            #tmp1和tmp2用来记录临时节点
            tmp1=cur.next
            tmp2=cur.next.next.next
            cur.next=tmp1.next
            cur.next.next=tmp1
            tmp1.next=tmp2
            cur=tmp1
        return pre.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21