算法入门很简单：链表题套路及精选题目（链表常见算法题）

算法入门很简单：链表题套路及精选题目（链表常见算法题）

链表介绍

链表（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}

硬做Set快慢指针

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. 链表设计

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。