关于go:链表高频算法题之Golang版思路清晰注释详尽

链表类的算法题在面试中是最常呈现的，题目尽管简略，但也非常考验面试者的逻辑思维和算法熟练度，以下通过几道常见的链表题来看看它们惯例的解法吧！（点击题目可到 leetcode 原题，不定时更新）

1、判断链表是否有环

思路

应用快慢指针遍历链表，快指针每次走 2 步，慢指针每次走 1 步，如果两者相遇，则有环，否则没有

package main

import "fmt"

type Node struct {
    Val  int
    Next *Node
}

func hasCycle(head *Node) bool {
    if head != nil {
        fast := head
        slow := head
        for fast != nil && fast.Next != nil {
            fast = fast.Next.Next
            slow = slow.Next
            if fast == slow {return true}
        }
    }
    return false
}

2、链表的两头结点

思路

应用快慢指针，快指针每次走 2 步，慢指针每次走 1 步，快指针走完了，慢指针所在的地位就是两头节点

func middleNode(head *Node) *Node {
    if head == nil || head.Next == nil {return nil}
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        head.Printf()}
    return slow
}

3、反转链表

思路

遍历链表，将每个节点的 next 指针指向前驱节点，遍历到最初的尾节点就是新的头节点

func (head *Node) reverse() *Node {
    if head == nil {return nil}
    var preNode *Node
    var newHead *Node
    curNode := head
    for curNode != nil {
        // 保留一份以后节点的后驱节点
        nextNode := curNode.next
        if nextNode == nil {newHead = curNode}
        // 设置以后节点的 next 为前驱节点
        curNode.next = preNode
        // 设置下一个节点的前驱节点为以后节点
        preNode = curNode
        // 指针后移
        curNode = nextNode
    }
    return newHead
}

4、合并两个有序链表

思路

双指针别离遍历两个链表，比拟两个节点的大小，将小的放到新的链表里，遍历完一遍后，将未遍历的局部指向新链表前面即可

func MergeTwoLists(list1 *Node, list2 *Node) *Node {
    // 初始化一个虚构的头节点
    newList := &Node{}
    p := newList
    p1 := list1
    p2 := list2
    // 遍历比照两个指针值的大小，有一个走完了就进行
    for p1 != nil && p2 != nil {
        // 将值小的节点接到 p 指针前面
        if p1.Val > p2.Val {
            p.Next = p2
            p2 = p2.Next
        } else {
            p.Next = p1
            p1 = p1.Next
        }
        // p 指针后退
        p = p.Next
    }
    // 将未比拟的残余节点都放到 p 指针前面
    if p1 != nil {p.Next = p1}
    if p2 != nil {p.Next = p2}
    // 返回虚构头节点的下一个节点就是真正的头节点
    return newList.Next
}

5、合并 K 个升序链表

思路

在合并两个升序链表的根底上顺次将这 K 个链表合并即可

func mergeKLists(lists []*ListNode) (res *ListNode) {
    for _, v := range lists {res = mergeTwoLists(res, v)
    }
    return res
}

//mergeTwoLists() 实现见上文

6、宰割链表

思路

遍历链表，依据节点的值将节点分到两个链表里，再将链表连贯到一起即可

func partition(head *Node, x int) *Node {
    curNode := head
    // 寄存值小于 x 的链表的虚构头节点
    dummy1 := &Node{}
    // 寄存值大于等于 x 节点的链表的虚构头节点
    dummy2 := &Node{}
    p1 := dummy1
    p2 := dummy2
    // 遍历链表，将原链表宰割为两个
    for curNode != nil {
        if curNode.Val < x {
            p1.Next = curNode
            p1 = p1.Next
        } else {
            p2.Next = curNode
            p2 = p2.Next
        }
        // 断开原链表的指针
        temp := curNode.Next
        curNode.Next = nil
        curNode = temp
    }
    // 连贯两个链表
    p1.Next = dummy2.Next
    return dummy1.Next
}

7、删除链表的倒数第 N 个结点

思路

1、要删除链表的倒数第 n 个结点就要先找到倒数第 n + 1 个结点
2、如何找：初始化两个双指针，先让 p1 走 k 个节点，而后让 p1、p2 一起走，p1 走到 nil 了，p2 所在的地位就是倒数第 k 个节点

func removeNthFromEnd(head *Node, n int) *Node {
    // 虚构头节点
    p1 := &Node{}
    p1.Next = head
    cur := getKthFromEnd(p1, n+1)
    cur.Next = cur.Next.Next
    return p1.Next
}

// 获取链表中倒数第 k 个节点
func getKthFromEnd(head *Node, k int) *Node {
    p1 := head
    p2 := head
    // 先让 p1 走 k 步
    for i := 0; i < k; i++ {p1 = p1.Next}
    for p1 != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    return p2
}