链表专题

1. 单链表的定义

单链表的典型定义如下：

type ListNode struct {
	Val  int
	Next *ListNode
}
复制代码

2. 单链表的基本操作

1. 插入

在给定的节点 prev 之后添加新值：

1. 初始化新节点 cur 

2. 将 cur 的 next 字段链接到 prev 的下一字段 next 

3. 将 prev 的 next 字段链接到 cur 

插入的时间复杂度为 O(1)，但是需要先遍历找到 prev，所以最坏时间复杂度为 O(n)

中间节点插入

func add(prev *ListNode, val int) {
    // 1. 初始化 cur
    cur := &ListNode{Val: val}
    // 2. cur的next指向prev的next
    cur.Next = prev.Next
    // 3. prev的next指向cur
    prev.Next = cur
}
复制代码

头插

func addHead(head *ListNode, val int) *ListNode {
    // 1. 初始化cur
    cur := &ListNode{Val: val}
    // 2. cur的next指向head
    cur.Next = head
    // 3. cur是新的head
    head = cur
    // 4. 将head返回
    return head
}
复制代码

2. 删除

删除现有节点 cur ：

1. 找到 cur 的上一个节点 prev 及其下一个节点 next 

2. 将 prev 的 next 指向 next 节点

删除的时间复杂度是 O(1)，但是必须遍历找出 prev 节点，所以时间复杂度是 O(n)

删除中间节点

func delete(prev *ListNode) {
    // 1. 找到要删除的节点 cur
	cur := prev.Next
    // 2. 将prev的next指向cur的next
	prev.Next = cur.Next
    // 3. 将cur的指向清空
	cur.Next = nil
}
复制代码

头删

func deleteHead(head *ListNode) *ListNode {
    // 1. 拿到新head
    newHead := head.Next
    // 2. 原来的head指向nil
    head.Next = nil
    // 3. 返回新head
    return newHead
}
复制代码

3. 遍历

func traversal(head *ListNode) {
	for head != nil {
		head = head.Next
	}
}
复制代码

3. 注意事项

1. 考虑操作节点的 prev，由于插入或删除都需要 prev，考虑这个节点怎么获取
2. 注意调用 Next 字段前，始终检查节点是否为空
3. 注意结束条件、边界值条件
4. 链表的常规测试用例，一般是奇或偶数个节点或单个节点

4. 常见考点

1. 快慢指针

定义两个指针，一个走得快（先走 or 一次走几步），另一个走得慢（一次走一步），可以解决如链表中的环，相交链表，找链表中倒数第几项等问题

1. 找环

快慢指针一起走，能撞到一起说明有环

// 注意 fast 起步为 head
fast, slow := head, head
for fast != slow {
    fast = fast.Next.Next
    slow = slow.Next.Next
}
复制代码

2. 找中间节点

找中间节点主要是为了将链表拆分成两段，进行后序操作，使用快慢指针找中间节点，而且通常都是前面多一点

// 注意 fast 起步为 head.Next，所以需要确保 head 存在，
// 这样处理不必考虑节点个数的奇偶对 slow 再进行特殊处理
fast, slow := head.Next, head
for fast != nil && fast.Next != nil {
    fast = fast.Next.Next
    slow = slow.Next
}
// 此时结束，slow 为后半段链表的 prev
// 1->2->3->4->5 fast 跳2步，slow到3,  rHead = 4->5
// 1->2->3->4->5->6 fast 跳2步，slow到3，rHead = 4->5->6
rHead := slow.Next
// 斩断前后链表的联系
slow.Next = nil
复制代码

2. 虚拟头节点

当需要对头节点进行特判，我们可以通过在头节点前面再加入一个虚拟头节点，让原来的头节点成为中间节点，从而统一插入和删除操作

1. 插入

func add(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    // 或者通过其他什么方式，获取要插入节点的前一个节点
    prev := dummy
    // 头插
    cur := &ListNode{Val: val}
    cur.Next = prev.Next
    prev.Next = cur
    return dummy.Next
}
复制代码

2. 删除

func delete(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    // 或者通过其他什么方式，获取要插入节点的前一个节点
    prev := dummy
    // 头删
    cur := prev.Next
    prev.Next = cur.Next
    cur.Next = nil
    return dummy.Next
}

复制代码

3. 翻转链表

翻转链表通常需要把链表分为三部分：翻转之前的部分、翻转的链表和翻转后的剩余部分

给断点的地方加上编号 a, b, c, d，想要的效果是这样：

b, c 是需要翻转部分的头和尾；a, d 是需要翻转链表部分的前驱和后继
整个翻转的流程如下：

1. 找到 a, b, c, d
2. 先把 c 和 d 的连接斩断
3. 以 b 为 head 送去翻转
4. a 指向 c，b 指向 d

练习题

707. 设计链表

type MyLinkedList struct {
    Val int
    Next *MyLinkedList
    // 定义链表长度，方便判断范围
    len int
}

func Constructor() MyLinkedList {
    return MyLinkedList{}
}

func (this *MyLinkedList) Get(index int) int {
    if this.len < index+1 {
        return -1
    }
    cur := this.Next
    for i := 0; i < index; i++ {
        cur = cur.Next
    }
    return cur.Val
}

func (this *MyLinkedList) AddAtHead(val int)  {
    cur := &MyLinkedList{Val: val}
    cur.Next = this.Next
    this.Next = cur
    this.len++
}

func (this *MyLinkedList) AddAtTail(val int)  {
    if this.len == 0 {
        this.AddAtHead(val)
    } else {
        prev := this
        for prev.Next != nil {
            prev = prev.Next
        }
        cur := &MyLinkedList{Val: val}
        prev.Next = cur
        this.len++
    }
}

func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index == this.len { 
        this.AddAtTail(val)
    } else if index <= 0 {
        this.AddAtHead(val)
    } else if index < this.len {
        prev := this
        for i := 0; i < index; i++ {
            prev = prev.Next
        }
        cur := &MyLinkedList{Val: val}
        cur.Next = prev.Next
        prev.Next = cur
        this.len++ 
    }
}

func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index < this.len && index >= 0 {
        prev := this
        for i := 0; i < index; i++ {
            prev = prev.Next
        }
        cur := prev.Next
        prev.Next = cur.Next
        cur.Next = nil
        this.len--
    }
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */
复制代码

141. 环形链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 快慢指针
func hasCycle(head *ListNode) bool {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}
复制代码

142. 环形链表 II

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 快慢指针找到环之后，再从环和head一起出发新节点，相遇则是环入口
func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            cur := head
            for cur != slow {
                cur = cur.Next
                slow = slow.Next
            }
            return cur
        }
    }
    return nil
}
复制代码

160. 相交链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// a 从 A 开始遍历，遍历完后从 B 开始遍历
// b 从 B 开始遍历，遍历完后从 A 开始遍历
// 相遇则是相交
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a, b := headA, headB
    for a != b {
        if a == nil {
            a = headB
        } else {
            a = a.Next
        }
        if b == nil {
            b = headA
        } else {
            b = b.Next
        }
    }
    return a
}
复制代码

剑指 Offer 22. 链表中倒数第k个节点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 快慢指针
// 快的指针先走 k 步，快慢指针再一起走，快指针走完了，慢指针就找到要返回的节点了
func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast := head
    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    slow := head
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}
复制代码

19. 删除链表的倒数第 N 个结点

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 虚拟头节点 + 快慢指针
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast := head
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    prev := dummy
    for fast != nil {
        fast = fast.Next
        prev = prev.Next
    }
    prev.Next = prev.Next.Next
    return dummy.Next
}
复制代码

21. 合并两个有序链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 归并排序的一部分
// 虚拟头节点 + 双指针
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }
    return dummy.Next
}
复制代码

83. 删除排序链表中的重复元素

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    cur := head 
    for cur != nil && cur.Next != nil {
        if cur.Val == cur.Next.Val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
}
复制代码

82. 删除排序链表中的重复元素 II

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head, Val: -999}
    prev := dummy
    for head != nil && head.Next != nil {
        // 出现重复
        if head.Val == head.Next.Val {
            next := head.Next
            // 可能多个重复值
            for next != nil && next.Val == head.Val {
                next = next.Next
            }
            prev.Next = next
            head = prev.Next
        } else {
            prev = head
            head = head.Next
        }
    }
    return dummy.Next
}
复制代码

206. 反转链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    for head != nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
复制代码

203. 移除链表元素

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 虚拟头节点
func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy
    for head != nil {
        if head.Val == val {
            prev.Next = prev.Next.Next
        } else {
            prev = head
        }
        head = head.Next
    }
    return dummy.Next
}
复制代码

234. 回文链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 双指针
// 快慢指针，快指针走两步，慢指针走一步
// 快指针走完时，慢指针走到中间，逆转后半段链表
// 前半段和逆转后的后半段链表对比
func isPalindrome(head *ListNode) bool {
    fast, slow := head.Next, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    right := reverseList(slow.Next)
    left := head
    for right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }
    return true
}
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    for head != nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
复制代码

2. 两数相加

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    c := 0
    dummy := &ListNode{}
    prev := dummy
    for l1 != nil || l2 != nil || c == 1 {
        count := c
        if l1 != nil {
            count += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            count += l2.Val
            l2 = l2.Next
        }
        c = count/10
        count = count%10
        prev.Next = &ListNode{Val: count}
        prev = prev.Next
    }
    return dummy.Next
}
复制代码

61. 旋转链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 快慢指针 + 虚拟头节点
// 快指针先走 k%len 步，慢指针再走
func rotateRight(head *ListNode, k int) *ListNode {
    len := 0
    cur := head
    for cur != nil {
        cur = cur.Next
        len++
    }
    if len <= 1 {
        return head
    }
    k = k % len
    if k == 0 {
        return head
    }
    fast := head
    for i := 0; i < k; i++ {
        fast = fast.Next
    }
    prev := head
    // 少跑一步，好处理节点关系
    for fast.Next != nil {
        fast = fast.Next
        prev = prev.Next
    }
    next := prev.Next
    prev.Next = nil
    fast.Next = head
    head = next
    return head
}
复制代码

86. 分隔链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 虚拟头节点
// 小于串一串
// 大于等于串一串
// 最后小的后面串上大于等于
func partition(head *ListNode, x int) *ListNode {
    ltHead := &ListNode{}
    geHead := &ListNode{}
    small, big := ltHead, geHead
    for head != nil {
        v := head.Val
        if v < x {
            small.Next = &ListNode{Val: v}
            small = small.Next
        } else {
            big.Next = &ListNode{Val: v}
            big = big.Next
        }
        head = head.Next
    }
    small.Next = geHead.Next
    return ltHead.Next
}
复制代码

92. 反转链表 II

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 拆出来，翻转后再放回去
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == right {
        return head
    }
    dummy := &ListNode{Next: head}
    prev := dummy
    // 到左前面
    for i := 0; i < left-1; i++ {
        prev = prev.Next
    }
    reverseHead := prev.Next
    reversePre := prev
    for i := 0; i < right-left+1; i++ {
        prev = prev.Next
    }
    // 保留后序节点
    next := prev.Next
    // 拆出来要翻转的链表
    prev.Next = nil
    newHead := reverseList(reverseHead)
    // 重新去连新的头
    reversePre.Next = newHead
    // 之前的头反转后变成最后一个了
    reverseHead.Next = next
    return dummy.Next
}
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    for head != nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
复制代码

138. 复制带随机指针的链表

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
// 建立原节点：新节点的映射
func copyRandomList(head *Node) *Node {
    m := make(map[*Node]*Node)
    cur := head
    for cur != nil {
        m[cur] = &Node{Val: cur.Val}
        cur = cur.Next
    }
    cur = head
    for cur != nil {
        m[cur].Next = m[cur.Next]
        m[cur].Random = m[cur.Random]
        cur = cur.Next
    }
    return m[head]
}
复制代码

143. 重排链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/*
    1->2->3->4->5

    按找回文数那样先拆成两个链表，前面保留多的
    1->2->3
    4->5
    翻转后一个链表
    1->2->3
    5->4
    按顺序排
    1->5->2->4->3
*/
func reorderList(head *ListNode)  {
    // 链表拆分成两个
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    rehead := slow.Next
    // 斩断前后两个链表
    slow.Next = nil
    // 后一个链表翻转
    newHead := reverseList(rehead)
    // 将两个链表归并
    cur := head
    curNew := newHead
    for cur != nil && curNew != nil {
        newNext := curNew.Next
        curNew.Next = cur.Next
        cur.Next = curNew
        curNew = newNext
        cur = cur.Next.Next
    }
}
func reverseList(head *ListNode) *ListNode {
    var newHead *ListNode
    for head != nil {
        next := head.Next
        head.Next = newHead
        newHead = head
        head = next
    }
    return newHead
}
复制代码

148. 排序链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 归并排序，使用快慢指针找中间节点，将链表拆成两段
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    fast, slow := head.Next, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    rHead := slow.Next
    slow.Next = nil
    left := sortList(head)
    right := sortList(rHead)
    return merge(left, right)
}
func merge(l *ListNode, r *ListNode) *ListNode {
    dummy := &ListNode{}
    prev := dummy
    for l != nil && r != nil {
        if l.Val < r.Val {
            prev.Next = l
            l = l.Next
        } else {
            prev.Next = r
            r = r.Next
        }
        prev = prev.Next
    }
    if l != nil {
        prev.Next = l
    }
    if r != nil {
        prev.Next = r
    }
    return dummy.Next
}
复制代码