1.链表的反转
一般也叫链表的逆序，比如
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
算法：
func reverseList(head *ListNode) *ListNode {
// 设置前驱节点
var prev = head
// 处理链表为空或只有一个元素的情况
if head == nil {
return head
}
if head.Next == nil{
return head
}
// 设定当前指针
cur := head.Next
for cur.Next != nil{
// 设置后驱指针
post := cur.Next
// 将当前指针的下一跳指向前驱节点
cur.Next = prev
// 将前驱设置为当前节点
prev = cur
// 将当前节点为后驱（后移）
cur = post
// 后驱指针后移
post = post.Next
}
// 处理最后一个节点
cur.Next = prev
// 处理原来的投节点（即当前的尾节点）
head.Next = nil
return cur
}
2. 合并两个链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
算法：
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var res *ListNode
// 当l1节点的值大于l2节点的值，那么res指向l2的节点，从l2开始遍历，反之从l1开始
if l1.Val >= l2.Val {
res = l2
res.Next = mergeTwoLists(l1, l2.Next)
} else {
res = l1
res.Next = mergeTwoLists(l1.Next, l2)
}
return res
}
3. 链表判环
给定一个链表，判断链表中是否有环。
算法：
func hasCycle(head *ListNode) bool {
fast,slow := head,head
for fast != nil && slow != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast==slow {
return true
}
}
return false
}
快慢指针的思想：
如果链表里有环，那么快指针和慢指针一定对相遇（指向相同的节点）
这里需要考虑下边界条件，如果快指针、慢指针或者快指针的下一跳为空则表示当前链表无环。
4. 链表的中间节点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
算法：
func middleNode(head *ListNode) *ListNode {
var step *ListNode
// 获取链表长度
var lens int
step = head
for step != nil {
lens++
step = step.Next
}
// 折半遍历
step = head
for i:=1;i<=lens/2;i++{
step = step.Next
}
return step
}
5. 删除中间节点
实现一种算法，删除单向链表中间的某个节点（除了第一个和最后一个节点，不一定是中间节点），假定你只能访问该节点。
思想：
不能获取链表头，那我们可以通过修改值实现中间节点的删除。
算法：
func deleteNode(node *ListNode) {
var head = node
var lens int
// 后面的元素值赋给自己
for head.Next != nil {
lens ++
head.Val = head.Next.Val
head = head.Next
}
head = node
// 删除最后一个节点
for i:=0; i<lens-1; i++{
head = head.Next
}
head.Next = nil
}
6. 两个链表的第一个公共节点
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
思想：
我们可以先计算两个链表的长度，然后让长的链表多走几步，走到两个链表后部分长度一样时，一个一个比较，直到找到相交的第一个元素。
算法：
func getIntersectionNode(headA, headB *ListNode) *ListNode {
var (
l1,l2,lose int
ha = headA
hb = headB
)
for h1:= headA; h1!=nil; h1=h1.Next{
l1++
}
for h2:= headB; h2!=nil; h2=h2.Next{
l2++
}
if l1 > l2 {
lose = l1 - l2
for i:=0;i< lose;i++ {
ha = ha.Next
}
}else {
lose = l2 - l1
for i:=0;i< lose;i++ {
hb = hb.Next
}
}
for ha != nil && hb != nil{
if ha == hb {
return ha
}
ha = ha.Next
hb = hb.Next
}
return nil
}
