链表类的算法题在面试中是最常呈现的，题目尽管简略，但也非常考验面试者的逻辑思维和算法熟练度，以下通过几道常见的链表题来看看它们惯例的解法吧！（点击题目可到 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
}