链表介绍

链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。

简单来说，「链表」 是实现线性表的链式存储结构的基础。

在链表中，数据元素之间的逻辑关系是通过指针来间接反映的。逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。

我们先来简单介绍一下链表结构的优缺点：

• 优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。
• 缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

套路总结

链表操作套路：链表不仅仅是穿针引线，还有双指针，虚拟节点，迭代和递归。

精选题目

1. 反转链表

def reverseList(self, head):
    cur, prev = head, None
    while cur:
      	cur.next, prev, cur = prev, cur, cur.next
    return prev

func reverseList(head *ListNode) *ListNode {

		if head == nil {
        return nil
    }

    cur := head
    var pre *ListNode

    for cur != nil {

        tmp := cur.Next
        cur.Next = pre
        pre = cur
        cur = tmp
    }
    return pre
}

2. 反转链表2

https://leetcode-cn.com/problems/reverse-linked-list-ii/

3. 两数相加

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

		dummy = tail = ListNode(None)
    sum = 0
    while l1 or l2 or sum:
        sum += (l1.val if l1 else 0) + (l2.val if l2 else 0)
        tail.next = ListNode(sum % 10)
        tail = tail.next
        sum // 10
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return dummy.next

4. 两两交换链表中的节点

def swapPairs(self, head: ListNode) -> ListNode:
		# 申请一个虚节点头
		pre, pre.next = self, head

    # 空 或者 只剩下一个节点
    while pre.next and pre.next.next:
        a = pre.next
        b = a.next

        pre.next, b.next, a.next = b, a, b.next
        pre = a

    return pre.next

func swapPairs(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return head
    }

    var (
        dummy *ListNode = &ListNode{0, head}
        temp = dummy
        cur = dummy.Next
    )

    for cur != nil && cur.Next != nil {
        temp.Next = cur.Next
        cur.Next = cur.Next.Next
        temp.Next.Next = cur
        
        temp = cur
        cur = cur.Next
    }
    return dummy.Next
}

5. 环形链表–判断是否有环

func hasCycle(head *ListNode) bool {
    first, second := head, head
    for first != nil && first.Next != nil {
        first = first.Next.Next
        second = second.Next
        if first == second {
            return true
        }
    }
    return false
}

1. 硬做
2. Set
3. 快慢指针

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

6. 环型链表2

7. K 个一组翻转链表

优先队列

class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        hair = ListNode(0)
        hair.next = head
        pre = hair

        while head:
            tail = pre
            # 查看剩余部分长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next
        
        return hair.next

func reverseKGroup(head *ListNode, k int) *ListNode {
    hair := &ListNode{Next: head}
    pre := hair

    for head != nil {
        tail := pre
        for i := 0; i < k; i++ {
            tail = tail.Next
            if tail == nil {
                return hair.Next
            }
        }
        nex := tail.Next
        head, tail = myReverse(head, tail)
        pre.Next = head
        tail.Next = nex
        pre = tail
        head = tail.Next
    }
    return hair.Next
}

func myReverse(head, tail *ListNode) (*ListNode, *ListNode) {
    prev := tail.Next
    p := head
    for prev != tail {
        nex := p.Next
        p.Next = prev
        prev = p
        p = nex
    }
    return tail, head
}

8. 插入排序

9. 链表排序

https://leetcode-cn.com/problems/sort-list/

10. 链表设计