数据结构与算法之单链表

数据结构与算法

最近看了些链表相关的理论，但实际操作时，还是会卡壳，这里记录自己一顿操作后对链表题的理解（一些技巧？）

理解指针（引用）

指针，就是C语言中的指针，像Java/Python没有指针概念的语言可以用引用代替，实际上可以大致理解成存储对象的内存地址。

对于指针（引用）的理解，引用《数据结构与算法之美》中的一句话：

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就可以找到这个变量。

这里举两个例子，像删除节点其实就是改变上一个节点指向的内存地址，改为下下个即可。

1
node.next = node.next.next

不过在新增节点中，需要注意插入操作的先后顺序，如果是像这样操作顺序，会导致指针丢失。

1
2
node.next = new_node
new_node.next = node.next

第一个步时，已将node已经指向new_node，导致第二步new_node又指向node，正确操作如下，先定义新节点的指向，再改变旧节点。

1
2
new_node.next = node.next
node.next = new_node

边缘情况

软件开发中，代码在边缘情况下，最容易导致BUG，链表中也不例外。要想链表代码能通过OJ，各种边缘情况是必须要考虑到了。这里列了最参见的4中边缘情况。

  1. 如果链表为空时，代码是否能正常工作？ 如果链表只包含一个
  2. 如果链表只包含一个结点时，代码是否能正常工作？
  3. 如果链表只包含两个结点时，代码是否能正常工作？
  4. 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

面试中参见的单链表题

最后列了5道面试经常遇到的单链表题

1
2
3
4
class ListNode(object):
    def __init__(self, x):
      self.val = x
      self.next = None

TIP: 有时候不太理解指针变化可以使用画图举例法，将指针变化通过画图更直观的呈现出来

合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def merge_wwo_lists(self, l1, l2):
        cur = ans = ListNode(0)
        while l1 and l2:
            if l1.val > l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1
                l1 = l1.next
            cur = cur.next
        cur.next = l1 or l2
        return ans.next

环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def has_cycle(self, head: ListNode) -> bool:
        """ 如果是环形链表，一快一慢的双指针最终会相遇 """
        if not head or not head.next:  # 防止head为空或只为一个值
            return False
        fast = head.next  # 快指针
        slow = head       # 慢指针
        while fast != slow:
            if not fast or not fast.next:
                return False
            fast = fast.next.next
            slow = slow.next
        return True

单链表反转

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def reverse_list(self, head):
        cur, ans = head, None
        while cur:
            temp = cur.next
            cur.next = ans
            ans = cur
            cur = temp
            # ans, ans.next, cur = cur, ans, cur.next
        return ans

链表的中间结点

1
2
3
4
5
6
7
class Solution:
    def middle_node(self, head):
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow

删除链表倒数第 n 个结点

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def remove_nth_from_end(self, head: ListNode, n: int) -> ListNode:
        node = ListNode(0)
        node.next = head
        left = right  = node
        for _ in range(n+1):
            right = right.next
        while right:
            left, right = left.next, right.next
        left.next = left.next.next
        return node.next