任务：

  1. 学习周期：8.10-8.16 号，共计 7 天。
  2. 学习专题：链表。链表的基本原理和操作非常重要，比如增、删、反转、合并、找中点等等。涉及到的技巧不多，大概就是dummy Node和快慢指针。个人觉得其终极原则就是链表这个数据结构的形式，以及这个形式造成了哪些优缺点。
  3. 训练题目：标红的重点再多巩固巩固

  • 6: 从头到尾打印链表

  • 18 : 删除链表的节点

  • 22:链表中倒数第A个节点

  • 23: 链表中环的入口节点

  • 24： 反转链表

  • 25: 合并两个排序的链表

6. 从头到尾打印链表(8.10)

image.png

1. 思路

  • 递归
    • 递归调用取值函数，合并数组
  • 辅助栈
    • 先进后出
  • 反转
    • 遍历链表，存到数组，把数组反转

      2. 递归

      1. class Solution:
      2. def reversPrint(self,head):
      3.    return self.reversPrint(head.next) + [head.val] if head else []
      1. int* reversePrint(struct ListNode* head, int* returnSize){
      2. if (head == NULL){
      3.    *returnSize = 0;
      4.    return NULL;
      5. }
      6. int* ans = reversePrint(head->next, returnSize);
      7. ans[(*returnSize)++] = head->val;
      8. return ans;
      9. }

      3. 辅助栈

      1. class Solution:
      2. def reversePrint(self, head):
      3.    stack = []
      4.    result = []
      5.    while head:
      6.        stack.append(head.val)
      7.        head = head.next
      8.    while stack:
      9.        result.append(stack.pop())
      10.    return result

      4. 反转

      1. class Solution:
      2. def reversePrint(self, head):
      3.    res = []
      4.    while head:
      5.        res.append(head.val)
      6.        head = head.next
      7.    return res[::-1]

      5. 总结

      这道题比较简单，原理都是遍历一下列表，可以直接在遍历中取逆序，也可以遍历后反转数组，还可以利用栈的先进后出，让所有元素出栈。

18. 删除链表的节点(8.11)

image.png

1. 思路

遍历链表，当节点的值等于val时跳过这个节点，跳过这个节点需要他的上一个值，

  • 可以直接在判断节点值时使用cur.next 来判断，跳过的步骤为 cur.next = cur.next.next
    • 单指针法
    • 边界条件
      • 头节点
      • 链表为空
  • 也可以使用双指针让一个指针指向节点的前一个节点，跳过的步骤为 pre.next = cur.next
    • 双指针法
    • 边界条件
      • 头节点

        2. 单链表

        ```python

        Definition for singly-linked list.

        class ListNode:

        def init(self, x):

        self.val = x

        self.next = None

class Solution: def deleteNode(self, head, val):

  1.     # 为空
  2.     if not head:
  3.         return head
  4.     # 头节点
  5.     if head.val == val :
  6.         return head.next
  7.     cur = head
  8.     while cur.next:
  9.         if cur.next.val == val:
  10.             cur.next = cur.next.next
  11.             break
  12.         cur = cur.next
  13.     return head
  1. <a name="GbgUj"></a>
  2. ### 3. 双链表
  3. ```python
  4. class Soluton:
  5.     def deleteNode(self,head,val):
  6.         # 头节点
  7.         if head.val == val:
  8.             return head.next
  9.            pre, cur = head, head.next
  10.         while cur:
  11.             if cur.val == val :
  12.                 pre.next = cur.next
  13.                 break
  14.             pre, cur = cur, cur.next
  15.         return head

4. 总结

这道题是删除链表中的节点，要通过匹配删除的话就需要知道节点的前一个节点，将前一个节点的next指向这个节点的next，即可以删除成功，在做题过程中要注意考虑边界情况，链表为空，删头节点，删尾节点。

22. 链表中倒数第k个节点(8.12)

image.png

1. 思路

  • 列表
    • 将链表遍历一遍，把每个节点存到列表中，返回列表后k个元素
  • 快慢指针
    • 快指针先走k步，然后快慢指针同时走，直到快指针走完，返回慢指针

      2. 列表存储

      ```python

      Definition for singly-linked list.

      class ListNode:

      def init(self, x):

      self.val = x

      self.next = None

class Solution: def getKthFromEnd(self, head, k): res = [] while head: res.append(head) head = head.next return res[-k]

  1. <a name="ENKij"></a>
  2. ### 3. 快慢指针
  3. ```python
  4. class Solution:
  5.     def getKthFromEnd(self, head, k):
  6.         fast, slow = head, head
  7.         for i in range(k):
  8.             fast = fast.next
  9.         while fast:
  10.             fast = fast.next
  11.             slow = slow.next
  12.         return slow

4. 总结

这道题比较经典的做法是使用快慢指针，使用数组列表的方法有点巧，快慢指针针对环的问题和这个问题会比较好一些。

141. 环形链表 一 (8.12)

今天完成了链表中倒数第k个节点，看下一个题正好是环形链表，可以练习一下快慢指针

  • 一 是判断是否有环
  • 二 是不仅判断是否有环，还要确定环在哪个位置

image.png

1. 思路

前提是链表中不含有重复元素

  • 快慢指针
    • 快指针一次走俩步
    • 慢指针一次走一步
    • 如果有环则快慢指针一定会相遇
  • 辅助空间
    • 遍历链表，存到集合中
      • 为什么是集合
        • 集合中不允许有重复元素
        • 可以直接判断是否在集合中
    • 判断是否有重复
    • 需要额外的空间

      2. 快慢指针

      ```python

      Definition for singly-linked list.

      class ListNode:

      def init(self, x):

      self.val = x

      self.next = None

class Solution: def hasCycle(self, head): fast, slow = head, head while fast and fast.next: fast = fast.next.next slow = slow.next if fast == slow: return True return False

  1. <a name="PpGUr"></a>
  2. ### 3. 辅助空间
  3. ```python
  4. class Solution:
  5.     def hasCycle(self, head):
  6.            temp = set()
  7.         while head;
  8.             if head in temp:
  9.                 return True:
  10.             temp.add(head)
  11.             head = head.next
  12.         return False

4. 总结

快慢指针想到了就不难，但是要考虑边界条件，while fast and fast.next ,这俩个判断条件不可以缺少。辅助空间法巧妙到用到了集合的特性

142. 环形链表 二 (8.12,13)

image.png

1. 思路

  • 如何来求解这个位置
  • 辅助空间
    • 用一个set把访问过的节点存起来
    • 如果有重复的，则返回节点
    • 遍历完没有，返回none
  • 双指针两次相遇
    • 第一次相遇判断是否有环
    • 第二次相遇寻找位置
    • image.png
      • 设slow走到环节点时走了k，那么fast走了2k，在环中走了k
      • 设fast在环中走了k之后还要走x，那么slow在环中走了x和fast相遇
      • 则第一次相遇时slow和fast距环节点k
      • 而head距环节点也为k
      • 则将一个指针从head走到环节点为k，slow走到环节点也为k
      • 第二次相遇在环节点

        2. 辅助空间

        1. class Solution:
        2. def detectCycle(self, head):
        3. temp = set()
        4. node = head
        5. while node:
        6.     if node in temp:
        7.         return node
        8.     else:
        9.         temp.add(node)
        10.         node = node.next
        11. return None

        3. 双指针二次相遇

        1. class Solution:
        2. def detectCycle(self, head):
        3. fast, slow = head, head
        4. while fast and fast.next:
        5.     fast = fast.next.next
        6.     slow = slow.next
        7.     if fast == slow:
        8.         fast = head
        9.         while fast != slow:
        10.             fast, slow = fast.next, slow.next
        11.         return fast
        12. return None

        4. 总结

        辅助空间和上一个判断是否有环没有太大区别，但是双指针法变成了二次相遇，如何可以让两个指针相遇到环节点的位置是需要好好思考的。

24. 反转链表(8.13)

image.png

1. 思路

  • 双指针
    • pre的next指向cur，实现一次局部反转
    • 反转后，每次往前移动一个位置
  • 递归
    • 找终止条件
      • head == null 或 head.next == null
    • 处理逻辑
      • head.next.next = head

        2. 双指针

        1. class Solution:
        2. def reverseList(self,head):
        3. pre = None
        4. cur = head
        5. while cur:
        6.     tmp = cur.next
        7.     cur.next = pre
        8.     pre = cur
        9.     cur = tmp
        10. return pre

        3. 递归

        1. class Solution:
        2. def reverseList(self, head):
        3. if (head === None or head.next == None):
        4.     return head
        5. cur = self.reverseList(head.next)
        6. head.next.next = head
        7. head.next = None
        8. return cur

        4. 总结

        反转链表，双指针比较好想一些，递归要注意结束条件和处理的逻辑，head.next.next = head，并且要把head.next 置空，否则会出现循环的错误

25. 合并两个排序的链表

image.png

1. 思路

  • 判断l1,l2的值，小一些的添加到新链表中，然后往回移动一位
  • 伪节点
    • 建立一个新链表，设置一个伪节点来返回链表
    • 判断l1和l2的值，添加到新链表的后面
  • 递归
    • 返回l1指向的结点和l2指向的结点中，值较小的结点
    • 递归调用

      2. 伪节点

      1. class Solution:
      2. def mergeTwoLists(self, l1, l2):
      3.    dummy = cur = ListNode(0)
      4.    while l1 and l2:
      5.        if l1.val < l2.val:
      6.            cur.next, l1 = l1, l1.next
      7.        else:
      8.            cur.next, l2 = l2, l2.next
      9.        cur = cur.next
      10.    cur.next = l1 if l1 else l2
      11.     return dummy.next

      3. 递归

      1. class Solution:
      2. def mergeTwoLists(self, l1, l2):
      3.    if not l1:
      4.        return l2
      5.    elif not l2:
      6.        return l1
      7.    elif l1.val < l2.val:
      8.        l1.next = self.mergeTwoLists(l1.next, l2)
      9.        return l1
      10.    else:
      11.        l2.next = self.mergeTwoLists(l1, l2.next)
      12.        return l2

      4. 总结

      这道题要注意哑节点的使用，是为了返回这个新链表，因为cur随着链表的添加已经到了最后。