链表类的算法题在面试中是最常呈现的，题目尽管简略，但也非常考验面试者的逻辑思维和算法熟练度，以下通过几道常见的链表题来看看它们惯例的解法吧！（点击题目可到leetcode原题，不定时更新）
1、判断链表是否有环
思路
应用快慢指针遍历链表，快指针每次走2步，慢指针每次走1步，如果两者相遇，则有环，否则没有
package mainimport "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}