链表 | 两两交换链表中的节点 | leecode刷题笔记

跟随carl代码随想录刷题
所用代码为python

---

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

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

输入：head = [1,2,3,4]
输出：[2,1,4,3]
⭐️示例 2：
输入：head = []
输出：[]
⭐️示例 3：
输入：head = [1]
输出：[1]

思路：

1. 定义虚拟头节点dummyhead，初始化dummyhead.next = head，临时指针cur = dummyhead

2. 终止条件：

   • 如果链表有偶数个节点，则当cur.next = None时，循环结束。
   • 如果链表有奇数个节点，则当cur.next.next = None时，循环结束。
   • eg：当链表为空时，因为cur位于虚拟头节点，所以cur.next = None，直接结束。
   • eg：当链表只有一个节点时，因为cur位于虚拟头节点，所以cur.next.next = None，直接结束。
   • ⭐️只有当这两个终止条件均不满足时，循环才执行。while((cur.next != None) and (cur.next.next != None)):
     • 注意：while条件判断时，两个条件不能写反！如果先写while (cur.next.next != None)，那么当cur.next = None时，cur.next.next会发生空指针异常。

3. 初始化：

   • temp = cur.next # 临时指针temp用于保存节点1的值
   • temp1 = cur.next.next.next # temp1保存节点3的值
   • cur.next = cur.next.next # 指向节点2
   • cur.next.next = temp # 节点2指向节点1
   • temp.next = temp1 # 节点1指向节点3
   • cur = cur.next.next # cur往后移动2位，开始下一次交换
   • return dummyhead.next

代码实现

# 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]:
        dummyhead = ListNode(next = head)  # 定义虚拟头节点
        cur = dummyhead

        while(cur.next and cur.next.next):
            temp = cur.next
            temp1 = cur.next.next.next

            cur.next = cur.next.next
            cur.next.next = temp
            temp.next = temp1

            cur = cur.next.next
        return dummyhead.next 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20