链表相关算法 - go语言实现

• 链表结构

type MyLinkedList struct {
    Val int
    Next *MyLinkedList
}

• 反转链表

func reverseList(head *ListNode) *ListNode {
    var pre,temp *ListNode
  //这里注意循环结束的条件
    for head != nil {      
        temp = head
        head = head.Next
        temp.Next = pre
        pre = temp
    }
    return temp 
}

• （移除节点）删除链表中等于给定值 val 的所有节点

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    pre_head := &ListNode{}
    pre_head.Next = head
    pre := pre_head
    cur := head
    for cur != nil {
        if cur.Val == val  {
            pre.Next = pre.Next.Next
        } else {
            pre = pre.Next
        }
        
        cur = cur.Next
    
    }
    return pre_head.Next
}

• 合并两个有序链表

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    l3 := &ListNode{}                              
    //注意：一定注意 var p *ListNode 和 a:=&ListNode{}的区别，
    //一个只能取Next，一个是空节点有val和next
    newHead := l3

    for l1 != nil && l2 != nil{
        if l1.Val <= l2.Val{
            l3.Next, l1, l3 = l1, l1.Next, l1
        }else{
            l3.Next, l2, l3 = l2, l2.Next, l2
        }
    }
    
    if l1 == nil{
        l3.Next = l2
    }else if l2 == nil{
        l3.Next = l1
    }
    return newHead.Next
}

• 链表成环检测

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

• 删除链表中倒数第k个节点

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    prev := &ListNode{}
    prev.Next = head
    fast := prev
    slow := prev
    for n>0 {
        fast = fast.Next
        n--
    }

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

• 删除链表中的节点(非末尾)

func deleteNode(node *ListNode) {
    *node = *(node.Next)
}