Loading... # Linked List ## 206.反转链表 ### 题目描述 反转一个单链表。 **示例:** ```bash 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL ``` 题目链接：https://leetcode-cn.com/problems/reverse-linked-list/ ### 解法一：迭代 ```python class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ pre = None cur = head # 跳出循环条件 while cur: # 暂存下个结点 temp_next = cur.next # 将当前结点指向前一个值 cur.next = pre # pre和cur都进一步 pre = cur cur = temp_next return pre ```  ### 解法二：递归 ```python class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or head.next == None: return head res = self.reverseList(head.next) # 将下个结点指向自己 head.next.next = head # 避免链表循环 head.next = None return res ``` ## 24.两两交换链表中的节点 ### 题目描述 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 **你不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。 **示例 1：**  ```bash 输入：head = [1,2,3,4] 输出：[2,1,4,3] ``` 题目链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs ### 解法一：借用栈 ```python class Solution(object): def swapPairs(self, head): """ :type head: ListNode :rtype: ListNode """ # Linked List题目特殊情况处理 if not head or head.next == None: return head # dummy结点 p = ListNode(-1) # 记录当前结点 cur = head # 记录头结点.等到程序结束返回head.next即可 head = p # 用stack保存每次迭代的两个节点 stack = [] while cur and cur.next: # 栈入 stack.append(cur) stack.append(cur.next) # 当前结点移动2个位置 cur = cur.next.next # 栈出操作，指向 p.next = stack.pop() p.next.next = stack.pop() # 移动p p = p.next.next # 边界条件判断，奇数时候会出现第一种情况，直接指向cur即可 if cur: p.next = cur else: p.next = None return head.next ``` ### 解法二：迭代 ```python class Solution(object): def swapPairs(self, head): # 增加一个特殊节点方便处理 p = ListNode(-1) # 创建a，b两个指针，这里还需要一个tmp指针 a,b,p.next,tmp = p,p,head,p while b.next and b.next.next: # a前进一位，b前进两位 a,b = a.next,b.next.next # 这步很关键，tmp指针用来处理边界条件的 # 假设链表是1->2->3->4，a指向1，b指向2 # 改变a和b的指向，于是就变成2->1，但是1指向谁呢？ # 1是不能指向2的next，1应该指向4，而循环迭代的时候一次处理2个节点 # 1和2的关系弄清楚了，3和4的关系也能弄清楚，但需要一个指针来处理 # 2->1，4->3的关系，tmp指针就是干这个用的 tmp.next,a.next,b.next = b,b.next,a # 现在链表就变成2->1->3->4 # tmp和b都指向1节点，等下次迭代的时候 # a就变成3，b就变成4，然后tmp就指向b，也就是1指向4 tmp,b = a,a return p.next ``` 这里的迭代做法从 LeetCode 题解抄过来，感觉有点绕，涉及到了三个指针，不是很能理解。 参考链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/dong-hua-yan-shi-24-liang-liang-jiao-huan-lian-bia/ ### 解法三：递归 ```python class Solution(object): def swapPairs(self, head): """ :type head: ListNode :rtype: ListNode """ # 边界条件判断 if not head or head.next == None: return head # 从第3个链表往后进行交换 third = self.swapPairs(head.next.next) # 从第3个链表往后都交换完了，我们只需要交换前两个链表即可, # 这里我们把链表分为3组，分别是第1个节点，第2个节点，后面 # 的所有节点，也就是1→2→3，我们要把它变为2→1→3 second = head.next head.next = third second.next = head return second ``` ## TODO 1. https://leetcode-cn.com/problems/linked-list-cycle 2. https://leetcode-cn.com/problems/linked-list-cycle-ii 3. https://leetcode-cn.com/problems/reverse-nodes-in-k-group/ Last modification：January 26th, 2021 at 03:56 am © 允许规范转载