链表

定义

type ListNode struct {
    Val int
    Next *ListNode
}

基础

null/nil 异常处理
dummy node 哑巴节点
快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点

例子

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

func deleteDuplicates(head *ListNode) *ListNode {
    current := head
    for current != nil {
        for current.Next != nil && current.Val == current.Next.Val {
            current.Next = current.Next.Next
        }
        current = current.Next
    }
    return head
}

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

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    dummy := &ListNode{Val: 0}
    dummy.Next = head
    head = dummy

    var rmVal int
    for head.Next != nil && head.Next.Next != nil {
        if head.Next.Val == head.Next.Next.Val {
            rmVal = head.Next.Val
            for head.Next != nil && head.Next.Val == rmVal {
                head.Next = head.Next.Next
            }
        } else {
            head = head.Next
        }
    }
    return dummy.Next
}

注意点 • A->B->C 删除 B，A.next = C • 删除用一个 Dummy Node 节点辅助（允许头节点可变） • 访问 X.next 、X.value 一定要保证 X != nil

206. 反转链表

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev

        prev = head
        head = temp
    }
    return prev
}

92. 反转链表 II

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil {
        return head
    }

    dummy := &ListNode{Val: 0}
    dummy.Next = head
    head = dummy

    var prev *ListNode
    i := 0
    for i < left {
        prev = head
        head = head.Next
        i++
    }

    var j = i
    var next *ListNode
    var mid = head
    for head != nil && j <= right {
        temp := head.Next
        head.Next = next
        next = head
        head = temp
        j++
    }
    prev.Next = next
    mid.Next = head
    return dummy.Next
}

21. 合并两个有序链表

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }

    var dummy = &ListNode{Val: 0}
    var head = &ListNode{Val: 0}
    dummy.Next = head
    
    for list1 != nil || list2 != nil {
        if list1 == nil {
            for list2 != nil {
                head.Next = list2
                list2 = list2.Next
                head = head.Next
            }
            break
        }
        if list2 == nil {
            for list1 != nil {
                head.Next = list1
                list1 = list1.Next
                head = head.Next
            }
            break
        }
        if list1.Val <= list2.Val {
            head.Next = list1
            list1 = list1.Next
        } else {
            head.Next = list2
            list2 = list2.Next
        }
        head = head.Next
    }
    return dummy.Next.Next
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    head := dummy

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            head.Next = list1
            list1 = list1.Next
        } else {
            head.Next = list2
            list2 = list2.Next
        }
        head = head.Next
    }

    for list1 != nil {
        head.Next = list1
        list1 = list1.Next
        head = head.Next
    }

    for list2 != nil {
        head.Next = list2
        list2 = list2.Next
        head = head.Next
    }
    return dummy.Next
}

86. 分隔链表

func partition(head *ListNode, x int) *ListNode {
    if head == nil {
        return head
    }

    headDummy := &ListNode{Val: 0}
    tailDummy := &ListNode{Val: 0}
    tail := tailDummy
    headDummy.Next = head
    head = headDummy
    for head.Next != nil {
        if head.Next.Val < x {
            head = head.Next
        } else {
            t := head.Next
            head.Next = head.Next.Next
            tail.Next = t
            tail = tail.Next
        }
    }
    tail.Next = nil
    head.Next = tailDummy.Next
    return headDummy.Next
}

148. 排序链表

func sortList(head *ListNode) *ListNode {
    return mergeSort(head)
}

func findMiddle(head *ListNode) *ListNode {
    slow := head
    fast := head.Next

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    head := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            head.Next = l1
            l1 = l1.Next
        } else {
            head.Next = l2
            l2 = l2.Next
        }
        head = head.Next
    }

    for l1 != nil {
        head.Next = l1
        l1 = l1.Next
        head = head.Next
    }
    for l2 != nil {
        head.Next = l2
        l2 = l2.Next
        head = head.Next
    }
    return dummy.Next
}

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

    middle := findMiddle(head)

    tail := middle.Next
    middle.Next = nil
    left := mergeSort(head)
    right := mergeSort(tail)
    result := mergeTwoLists(left, right)
    return result
}

143. 重排链表

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

    middle := findMiddle(head)
    tail := middle.Next
    middle.Next = nil

    tail = reverseList(tail)

    head = mergeTwoLists(head, tail)
}

func findMiddle(head *ListNode) *ListNode {
    slow := head
    fast := head.Next

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev

        prev = head 
        head = temp
    }
    return prev
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    head := dummy
    for l1 != nil && l2 != nil {
        head.Next = l1
        l1 = l1.Next
        head = head.Next
        head.Next = l2
        l2 = l2.Next
        head = head.Next
    }

    for l1 != nil {
        head.Next = l1
        l1 = l1.Next
        head = head.Next
    }
    for l2 != nil {
        head.Next = l2
        l2 = l2.Next
        head = head.Next
    }
    return dummy.Next
}

141. 环形链表

func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }
    
    fast := head.Next
    slow := head

    for fast != nil && fast.Next != nil {
        if fast == slow {
            return true
        }
        fast = fast.Next.Next
        slow = slow.Next
    }
    return false
}

142. 环形链表 II

func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    fast := head.Next
    slow := head

    for fast != nil && fast.Next != nil {
        if fast == slow {
            fast = head
            slow = slow.Next
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return slow
        }
        fast = fast.Next.Next
        slow = slow.Next
    }
    return nil
}

指针比较时直接比较对象，不要用值比较，链表中有可能存在重复值情况;
第一次相交后，快指针需要从下一个节点开始和头指针一起匀速移动.

另外一种方式是 fast=head,slow=head

func detectCycle(head *ListNode) *ListNode {
    // 思路：快慢指针，快慢相遇之后，其中一个指针回到头，快慢指针步调一致一起移动，相遇点即为入环点
    // nb+a=2nb+a
    if head == nil {
        return head
    }
    fast := head
    slow := head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            // 指针重新从头开始移动
            fast = head
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return slow
        }
    }
    return nil
}

这两种方式不同点在于，一般用 fast=head.Next 较多，因为这样可以知道中点的上一个节点，可以用来删除等操作。

fast 如果初始化为 head.Next 则中点在 slow.Next;
fast 初始化为 head,则中点在 slow.

234. 回文链表

func isPalindrome(head *ListNode) bool {
    // 1 2 nil
    // 1 2 1 nil
    // 1 2 2 1 nil
    if head==nil{
        return true
    }
    slow:=head
    // fast如果初始化为head.Next则中点在slow.Next
    // fast初始化为head,则中点在slow
    fast:=head.Next
    for fast!=nil&&fast.Next!=nil{
        fast=fast.Next.Next
        slow=slow.Next
    }

    tail:=reverse(slow.Next)
    // 断开两个链表(需要用到中点前一个节点)
    slow.Next=nil
    for head!=nil&&tail!=nil{
        if head.Val!=tail.Val{
            return false
        }
        head=head.Next
        tail=tail.Next
    }
    return true

}

func reverse(head *ListNode)*ListNode{
    // 1->2->3
    if head==nil{
        return head
    }
    var prev *ListNode
    for head!=nil{
        t:=head.Next
        head.Next=prev
        prev=head
        head=t
    }
    return prev
}

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

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }

    cur := head
    for cur != nil {
        clone := &Node{Val: cur.Val, Next: cur.Next}
        temp := cur.Next
        cur.Next = clone
        cur = temp
    }

    cur = head 
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }

    cur = head
    cloneHead := cur.Next
    for cur != nil && cur.Next != nil {
        temp := cur.Next
        cur.Next = cur.Next.Next
        cur = temp
    }
    return cloneHead
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

链表.md

链表.md

链表

定义

基础

例子

Files

链表.md

Latest commit

History

链表.md

File metadata and controls

链表

定义

基础

例子