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

Leetcode
725 词

设置好虚拟头节点，想好断开的位置的时候，前后连的节点怎么处理。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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: Optional[ListNode]) -> Optional[ListNode]:

        dummy=ListNode(0,head)

        dummy_head=dummy

        tail=head

        while tail and tail.next:

            q=tail.next

            temp=q.next

            tail.next=temp

            dummy.next=q

            q.next=tail

            tail.next=temp

            dummy=tail

            tail=tail.next

        return dummy_head.next

首先先设置好虚拟头节点，想好断开的位置的时候，前后连的节点怎么处理。

  • 保证了前驱→新头这一条边不会断，链表保持连通。

  • 用 temp 保存下一段，避免丢失后续链表。

  • 循环条件 while tail and tail.next: 避免空指针错误。

  • 每轮交换后把 dummy、tail 一起前移，循环能正确推进

符号：

  • dummy：本轮要交换的两个节点前面的那个节点（前驱）

  • tail：这一对的第一个节点（旧头）

  • q：这一对的第二个节点（要换到前面的新头）

  • temp：下一段链表的起点（可能是下一个 pair 的第一个节点，也可能是 None）