本文用于收集 leetcode 题解，以训练思维，同时精进算法

刷题正确打开方式

刷起来：千里之行始于足下
按算法分类来选题
难度循序渐进
有思路：先不考虑算法是否高效，能解决就行。不要一味追求高效，而迟迟不动手，最后连一种解法都没有。性能高效是优化出来的，没有一个基础的解法，哪来优化的对象！
- 暴力法是思路的起点
- 不要一看题，觉得不会，或者没思路就急着搜答案，而是要尝试思考。多在草稿纸上写写画画，实在想不出来再去搜
- 多题一解：解法迁移
- 一题多解：多维度思考和尝试，每种算法思想都设法熟练
动手实现：不要有思路或者看懂了就认为自己会了，只有动手去实现才能提高代码能力和快速思维能力
不断总结完善补充：总结算法思想、算法思维模版等，吃透每一种算法和思想
坚持刷下去，不断重复

算法思想

八大算法基础思想

链表

判断链表是否存在环

题目要求

标记法

遍历过程中遇到已经出现过的节点，则认为存在环

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
   mp := make(map[*ListNode]struct{})
   for head != nil {
       if _, ok := mp[head]; ok {
           return true
       }

       mp[head] = struct{}{}
       head = head.Next
   } 

   return false
}

快慢双指针法

快慢指针同时遍历，快慢指针能相遇则存在环

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

        if slow == fast {
            return true
        }
    }

   return false
}

链表有环则找出线与环的交接点

题目要求

标记法

遍历过程中遇到已经出现过的节点，则认为存在环（同上一题，返回值做调整）

  
func detectCycle(head *ListNode) *ListNode {
   mp := make(map[*ListNode]struct{})
   for head != nil {
       if _, ok := mp[head]; ok {
           return head
       }

       mp[head] = struct{}{}
       head = head.Next
   } 

   return nil
}

快慢双指针法

快慢指针找到相遇节点
慢指针回到起点，快指针停留在相遇节点
快慢指针以相同速度前进，再次相遇则会交接点

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil {
        slow = slow.Next
        if fast.Next != nil {
            fast = fast.Next.Next
        } else {
            fast = nil
            break
        }

        if slow == fast {
            break
        }
    }

    if fast == nil {
        return nil
    }

    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }

   return slow
}

找出相交单链表的交点

题目要求

方法一

对齐长短两个链表的起点(两链表从该起点到终点的长度相等)，同速前进，首个相遇节点即为交点。

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    var lenA, lenB int
    pA, pB := headA, headB
    for pA != nil {
        lenA++
        pA = pA.Next
    }

    for pB != nil {
        lenB++
        pB = pB.Next
    }

    pA, pB = headA, headB
    switch {
        case lenA > lenB:
        for lenA > lenB {
            lenB++
            pA = pA.Next
        }
        case lenA < lenB:
        for lenA < lenB {
            lenA++
            pB = pB.Next
        }
        default:
    }

    for pA != nil {
        if pA == pB {
            return pA
        }

        pA = pA.Next
        pB = pB.Next
    }

    return nil
}

方法二

假设两个链表的尾部有条虚线连接着对方的头部，这样连个链表相当于是等长的，相遇时即为交点（思想类似方法一，但方法一更直观一点）

  
func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode {
    pA, pB := headA, headB

    for pA != pB {
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }

        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }

    return pA
}

方法三

用map存储已经遍历过的两链表节点，正在遍历的当前节点已经遍历过，说明该节点即为交点

  
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pA, pB := headA, headB
    mp := make(map[*ListNode]struct{})
    for pA != nil || pB != nil {
        if pA != nil {
            if _, ok := mp[pA]; ok {
                return pA
            }

            mp[pA] = struct{}{}
            pA = pA.Next
        }

        if pB != nil {
            if _, ok := mp[pB]; ok {
                return pB
            }

            mp[pB] = struct{}{}
            pB = pB.Next
        }
    }

    return nil
}

方法四

把较短的链表A视为首尾相连的环，从另一个链表B出发，则整体上可以认为是带环的一个链表。转化成了6字形的环形链表问题，求环形的入口节点。

  
func makeCirleLink(head *ListNode) *ListNode {
    var last *ListNode
    p := head
    for p != nil {
        if p.Next == nil {
            last = p
            last.Next = head
            break
        }

        p = p.Next
    }

    if last == nil {
        return nil
    }

    return last
}

func findCirleEntry(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil {
        if fast.Next == nil {
            fast = nil
            break
        }

        fast = fast.Next.Next
        slow = slow.Next

        if slow == fast {
            break
        }
    }

    if fast == nil {
        return nil
    }

    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }

    return slow
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lastA := makeCirleLink(headA)
    if lastA == nil {
        return nil
    }

    defer func() { lastA.Next = nil }()
    return findCirleEntry(headB)
}

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

题目要求，这个题目的关键是定位到指定节点。

方法一

先反转链表(头插法)，删除此时的顺数第N个节点，再次反转即可

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(head *ListNode) *ListNode {
    p := &ListNode{Next: nil}
    tmp := head
    for head != nil {
        tmp = head.Next
        head.Next = p.Next
        p.Next = head
        head = tmp
    }

    return p
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil {
        return nil
    }

    r := reverseList(head)
    p := r

    n--
    for n > 0 {
        n--
        p = p.Next
    }

    if p == nil {
        return nil
    }

    p.Next = p.Next.Next
    r = reverseList(r.Next)
    return r.Next 
}

方法二

（逆向思维）算出整个链表的长度 len，把倒数第 N 个转化成顺数第 len - N + 1

  
func listLen(head *ListNode) int {
    var size int
    for head != nil {
        size++
        head = head.Next
    }

    return size
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    size := listLen(head)
    if n <= 0 || n > size || head == nil {
        return nil
    }

    m := size - n
    p := &ListNode{}
    ret := p
    p.Next = head

    for m > 0 {
        m--
        p = p.Next
    }


    p.Next = p.Next.Next

    return ret.Next
}

方法三

（把只能顺序访问的结构转化为可随机访问的结构）遍历链表时把所有节点地址存入一个数组中，倒数定位第 N+1，将其指向倒数第 N-1 个节点即可

  
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return nil
    }

    stack := make([]*ListNode, 0, 30)
    p := head

    for p != nil {
        stack = append(stack, p)
        p = p.Next
    }

    if len(stack) < n {
        return nil
    }

    m := len(stack) - n - 1
    if m < 0 {
        return head.Next
    }

    stack[m].Next = stack[m+1].Next
    return head
}

方法四

（快慢双指针法）以N个节点作为步长来遍历，直到链尾，则此时步长区间的左端点即可定位到对应的节点。快慢可以是遍历的间距上的快慢，也可以是起跑线的先后。

  
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil {
        return nil
    }

    p := head
    for n > 0 && p != nil {
        n--
        p = p.Next
    }

    if n > 0 {
        return nil
    }

    if p == nil {
        return head.Next
    }

    q := head
    for p.Next != nil {
        p = p.Next
        q = q.Next
    }

    q.Next = q.Next.Next
    return head 
}

合并两个有序链表

题目要求

哨兵迭代法

不哨兵迭代法：断重复相同的步骤直到达到目的

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    result := &ListNode{}
    p := result
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            p.Next = list1
            list1 = list1.Next
        } else {
            p.Next = list2
            list2 = list2.Next
        }

        p = p.Next
    }

    if list1 != nil {
        p.Next = list1
    }

    if list2 != nil {
        p.Next = list2
    }

    return result.Next
}

递归法

递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。说白了就是：

原问题是什么：输入、映射关系、输出
缩小规模后子问题是什么（需要和原问题一致，只是规模不同）
如何缩小规模，即递归前进，f(n-1) 与 f(n) 之间的关系，这种关系成立的条件是什么
最基本问题是什么：即边界条件(退出条件)，如 f(0)、f(1)等

原问题是合并两个链表，当我们提取出最小值的时候，子问题就可以变成合并缩小规模后的两条链表，例如合并两个链表list1=[1,2,4,8],list2=[2,3,6,7]，我们提取出当前最小值是list1的头节点，子问题就变成合并两个链表list1=[2,4,8],list2=[2,3,6,7],然后将list1的头节点拼接上即可

上述问题实际上，可以改为 listNew.next = merge(list1.next, list2);「假设 list1的头结点比list2的头结点值小的情况下」，和总问题的出入参一样，就可以采用递归的解法。递归思想可参考全面理解递归、递归思想(总结)

算法分解如下：

最基本问题或边界条件

  
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }

    if list2 == nil {
        return list1
    }
}

原问题和子问题的共性（输入、映射关系、输出）：函数入参、函数功能、返回值

  
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1.Val < list2.Val {
        return list1
    }

    return list2
}

递归前进：原问题不断缩小规模直至边界退出

  
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    }

    list2.Next = mergeTwoLists(list2.Next, list1)
    return list2
}

完整解法

  
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }

    if list2 == nil {
        return list1
    }

    if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    }

    list2.Next = mergeTwoLists(list2.Next, list1)
    return list2
}

合并K个有序链表

题目要求

逐一两两合并

我们可以先前两个合并，合并好了之后再跟第三个、然后第四个直到第k个。至于两个有序链表合并的若干方法，可以参考上一题。

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeTwoList(listA, listB *ListNode) *ListNode {
    if listA == nil {
        return listB
    }

    if listB == nil {
        return listA
    }

    head := &ListNode{}
    ret := head
    for listA != nil && listB != nil {
        if listA.Val < listB.Val {
            ret.Next = listA
            listA = listA.Next
        } else {
            ret.Next = listB
            listB = listB.Next           
        }

        ret = ret.Next
    }

    tmp := listA
    if listB != nil {
        tmp = listB
    }

    ret.Next = tmp
    return head.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    var ret *ListNode
    for i := 0; i < len(lists); i++ {
        ret = mergeTwoList(ret, lists[i])
    }

    return ret
}

分治递归法(归并排序)

不断分治，直到只剩两个链表，再合并两个链表

方法一

  
func mergeTwoList(listA, listB *ListNode) *ListNode {
    if listA == nil {
        return listB
    }

    if listB == nil {
        return listA
    }

    head := &ListNode{}
    ret := head
    for listA != nil && listB != nil {
        if listA.Val < listB.Val {
            ret.Next = listA
            listA = listA.Next
        } else {
            ret.Next = listB
            listB = listB.Next           
        }

        ret = ret.Next
    }

    tmp := listA
    if listB != nil {
        tmp = listB
    }

    ret.Next = tmp
    return head.Next
}

func merge(lists []*ListNode, left, right int) *ListNode {
    if left == right {
        return lists[left]
    }

    mid := left + (right - left) / 2
    l := merge(lists, left, mid)
    r := merge(lists, mid + 1, right)

    return mergeTwoList(l, r)
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    return merge(lists, 0, len(lists)-1)
}

方法二

  
func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    switch n {
    case 0:
        return nil
    case 1:
        return lists[0]
    case 2:
        //针对两个链表进行归并排序
        return mergeTwoList(lists[0], lists[1])
    default:
        key := n / 2
        //数组拆分,使下一次递归的lists的长度=2

        //优化思路: mergeKLists(lists[:key]),使用Goroutine+channel进行并发合并(归并排序的特点)
        return mergeKLists([]*ListNode{mergeKLists(lists[:key]), mergeKLists(lists[key:])})
    }
}

func mergeTwoList(listA, listB *ListNode) *ListNode {
    if listA == nil {
        return listB
    }

    if listB == nil {
        return listA
    }

    head := &ListNode{}
    ret := head
    for listA != nil && listB != nil {
        if listA.Val < listB.Val {
            ret.Next = listA
            listA = listA.Next
        } else {
            ret.Next = listB
            listB = listB.Next           
        }

        ret = ret.Next
    }

    tmp := listA
    if listB != nil {
        tmp = listB
    }

    ret.Next = tmp
    return head.Next
}

方法三

  
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists)==0{
        return nil
    }
    if len(lists) == 1{
        return lists[0]
    }
    if len(lists) == 2{
        return mergeTwoLists(lists[0],lists[1])
    }
    mid := len(lists)/2
    lists1 := lists[:mid]
    lists2 := lists[mid:]
    return mergeTwoLists(mergeKLists(lists1),mergeKLists(lists2))
}

func mergeTwoLists(l1,l2 *ListNode) *ListNode{
    if l1==nil{return l2}
    if l2==nil{return l1}
    pre := &ListNode{Val:0,Next:nil}
    cur := pre
        if l1.Val>l2.Val{
            cur.Next = l2
            cur.Next.Next = mergeTwoLists(l2.Next,l1)
        }else{
            cur.Next = l1
            cur.Next.Next = mergeTwoLists(l1.Next,l2)
        }
    return pre.Next
}

方法四

  
func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if n == 0 {
        return nil
    } 
    // sz/2 > n时，意味着已经合并过一次 size > n，而该合并仅需一次
    for sz := 2; sz/2 < n; sz *= 2 {
        for i := 0; i < n; i += sz {
            if i+sz/2 < n{
                lists[i] = mergeTwoLists(lists[i], lists[i+sz/2])
            }
        }
    }
    return lists[0]
}

func mergeTwoLists (list1, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    pre := dummy
    for {
        if list1 == nil {
            pre.Next = list2
            break
        } else if list2 == nil {
            pre.Next = list1
            break
        } else if list1.Val <= list2.Val {
            pre.Next, pre = list1, list1
            list1 = list1.Next
        } else {
            pre.Next, pre = list2, list2
            list2 = list2.Next
        }
    }
    return dummy.Next
}

方法五：二路归并

  
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) < 1 {
        return nil
    }

    queue := lists
    for len(queue) > 1 {
        var nextQueue []*ListNode
        current, end := 0, len(queue)-1
        for current <= end {
            node := queue[current]

            // 当前这一轮，如果只有最后一个节点，不需要合并
            if (current + 1) > end {
                nextQueue = append(nextQueue, node)
                queue = nextQueue
                break
            }

            nextNode := queue[current+1]

            // 合并两个链表
            newNode := mergeTwoLists(node, nextNode)
            nextQueue = append(nextQueue, newNode)

            if current+1 == end {
                queue = nextQueue
            }

            current += 2
        }
    }

    return queue[0]
}

func mergeTwoLists(l1,l2 *ListNode) *ListNode {
    newNode := ListNode{Val: -1, Next: nil}
    markPoint := &newNode

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            markPoint.Next = l1
            l1 = l1.Next
        } else {
            markPoint.Next = l2
            l2 = l2.Next
        }
        markPoint = markPoint.Next
    }

    if l1 == nil {
        markPoint.Next = l2
    } else {
        markPoint.Next = l1
    }

    return newNode.Next
}

方法六：多协程归并

  
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{}
	now := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			now.Next , l1 = l1 , l1.Next
		}else{
			now.Next , l2 = l2 , l2.Next
		}
		now = now.Next
	}
	if l1 == nil {
		now.Next = l2
	}else {
		now.Next = l1
	}
	return head.Next
}

// 多线程
// 思路 ： map - reduce
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
		return nil
	}
	var receiver *ListNode
	latch := &sync.WaitGroup{}
	latch.Add(1)
	mergeKListsByGo(lists,0,len(lists)-1,latch,&receiver)
	return receiver
}

func mergeKListsByGo(lists []*ListNode , left , right int , latch *sync.WaitGroup , receiver **ListNode) {
	defer latch.Done()
	if left == right {
		*receiver = lists[left]
		return
	}
	if left == right - 1 {
		*receiver = mergeTwoLists(lists[left],lists[right])
		return
	}
	newLatch := &sync.WaitGroup{}
	newLatch.Add(2)
	var lr , rr *ListNode
	middle := (left + right) / 2
	go mergeKListsByGo(lists , left , middle ,newLatch , &lr)
	go mergeKListsByGo(lists , middle+1 , right ,newLatch , &rr)
	newLatch.Wait()
	*receiver = mergeTwoLists(lr,rr)
}

K指针

在”合并两个有序链表”中，相对较小的节点链入新链表，且对应链表顺链移动，直到其中某个链表结束。对于K个有序链表，我们可以获取其中最小的节点，链入新链表，且对应链表顺链移动，直到只剩下一个非空链表为止。

方法一：slice存放K个指针

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

 func getMinNode(lists []*ListNode) int {
    minVal := math.MaxInt
    minIdx := -1
    for i, node := range lists {
        if node == nil {
            continue
        }

        if node.Val < minVal {
            minIdx = i
            minVal = node.Val
        }
    }

    return minIdx
 }

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    head := &ListNode{}
    p := head
    curListNode := make([]*ListNode, 0, len(lists))
    for _, v := range lists {
        if v == nil {
            continue
        }

        curListNode = append(curListNode, v)
    }

    for {
        minIdx := getMinNode(curListNode)
        if minIdx < 0 {
            return head.Next
        }

        p.Next = curListNode[minIdx]
        p = p.Next
        if cur := curListNode[minIdx].Next; cur == nil {
            if minIdx == len(curListNode) - 1 {
                curListNode = curListNode[:minIdx]
            } else {
                curListNode = append(curListNode[:minIdx], curListNode[minIdx+1:]...)
            }

            continue
        }

        if len(curListNode) < 2 {
            break
        }
        
        curListNode[minIdx] = curListNode[minIdx].Next
    }

    return head.Next
}

方法二：链表存放K指针

  
type nodeInfo struct {
    node *ListNode
    next *nodeInfo
}

 func getMinNode(head *nodeInfo) *ListNode {
    minVal := math.MaxInt
    var minNode *nodeInfo
    for head.next != nil {
        if head.next.node == nil {
            head.next = head.next.next
            continue
        }

        if val := head.next.node.Val; minVal > val {
            minVal = val
            minNode = head.next
        }

        head = head.next
    }

    if minNode == nil {
        return nil
    }

    ret := minNode.node
    minNode.node = minNode.node.Next
    return ret
 }

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    head := &ListNode{}
    p := head

    curListNodeHead := &nodeInfo{}
    curListNode := curListNodeHead
    for _, v := range lists {
        if v == nil {
            continue
        }

        curListNode.next = &nodeInfo{
            node: v,
        }

        curListNode = curListNode.next
    }

    for {
        minNode := getMinNode(curListNodeHead)
        if minNode == nil || minNode.Val == math.MaxInt {
            break
        }

        p.Next = minNode
        p = p.Next
        if curListNodeHead.next == nil || curListNodeHead.next.next == nil {
            break
        }
    }

    return head.Next
}

从运行时间来看，方法一笔方法二要高效得多（切片删除元素比链表删除元素还快？）

优先队列(二叉堆)

在“合并两个有序链表”时，我们把相对较小的节点链入新链表，直到某个链表结束。合并K个有序链表也是类似的，只不过要在K个链表节点得到最小节点（K个链表中每个链表各出一个节点），然后链入新链表，直到只剩下一个链表有节点或者都没有节点为止。

从K个节点获取最小节点这个过程，可以使用优先队列(二叉堆)这种数据结构。复杂度比“逐一两两合并” 的要小很多。

方法一：标准库heap接口实现小顶堆

  
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    
    dummy := &ListNode{-1, nil}
    p := dummy
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    for _, head := range lists {
        if head != nil {
            heap.Push(&pq, head)
        }
    }

    for pq.Len() > 0 {
        node := heap.Pop(&pq).(*ListNode)
        p.Next = node
        if node.Next != nil {
            heap.Push(&pq, node.Next)
        }

        p = p.Next
    }
    return dummy.Next
}

type PriorityQueue []*ListNode

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    node := x.(*ListNode)
    *pq = append(*pq, node)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    node := old[n-1]
    *pq = old[0 : n-1]
    return node
}

方法二：标准库二叉堆接口实现

  
func mergeKLists(lists []*ListNode) *ListNode {
    heap := binaryheap.NewWith(compare)
    // push heads to heap
    for _, node := range lists{
        if node != nil{
            heap.Push(node)
        }
    }
    dummy := &ListNode{}
    node := dummy
    for heap.Size() > 0{
        tmp,_ := heap.Pop()
        node.Next = tmp.(*ListNode)
        node = node.Next
        if node.Next != nil{
            heap.Push(node.Next)
        }
    }
    return dummy.Next
}

func compare(a,b interface{}) int{
    x := a.(*ListNode)
    y := b.(*ListNode)

    if x.Val > y.Val{return 1}
    if x.Val < y.Val{return -1}
    return 0
}

方法三：自行实现小顶堆

``go func mergeKLists(lists []*ListNode) *ListNode { // 1.初始化变量 // 生成一个基于小顶堆的优先级队列 queue := priorityQueue{} // 初始化结果链表头结点 head := &ListNode{} p := head

// 2.首先将所有链表的首元节点入队，从而初始化构建一个基于小顶堆的优先级队列
for _, list := range lists {
	if list != nil {
		queue.push(list)
	}
}

// 3.此时堆顶元素就是最小值，循环获取堆顶元素
for len(queue) > 0 {
	// 将堆顶元素连接到新链表头结点的下一个节点
	minNode := queue.pop()
	p.Next = minNode
	p = p.Next
	// 将堆顶元素原来所属链表的下一个节点入队，并调整堆结构
	if minNode.Next != nil {
		queue.push(minNode.Next)
	}
}

// 4.循环执行上述操作，直到所有的链表都完成入队出队，返回结果链表
return head.Next }

// 优先级队列 type priorityQueue []*ListNode

// 入队 func (p priorityQueue) push(node *ListNode) { // 将元素入堆 *p = append(p, node) // 上浮调整 p.upAdjust() }

// 出队 func (p priorityQueue) pop() *ListNode { // 获取堆顶元素 top := (p)[0] // 删除堆顶元素，并将堆中最后一个元素移到堆顶 n := len(p) - 1 (p)[0], (p)[n] = (p)[n], (p)[0] *p = (p)[:n] // 如果堆的大小不为0，则对堆进行下沉调整 if len(*p) > 0 { p.downAdjust() } // 返回堆顶元素 return top }

// 插入元素时，上浮调整 func (p priorityQueue) upAdjust() { // 获取新插入元素的索引（新插入的元素在堆的最后一个位置） childrenIndex := len(p) - 1 // 获取新插入元素父节点的索引，父节点索引 = ( 左/右孩子节点索引 - 1) / 2 parentIndex := (childrenIndex - 1) / 2 // 记录新插入元素的值，用于比较和最后的赋值，而不需要每一步都进行交换 temp := (*p)[childrenIndex]

// 循环上浮判断并调整
// 如果新元素索引越界或父节点元素的值<=新元素的值，说明堆调整完毕，跳出循环
for childrenIndex > 0 && (*p)[parentIndex].Val > temp.Val {
	// 将父节点的值赋值到新元素位置
	(*p)[childrenIndex] = (*p)[parentIndex]
	// 获取上浮的下一轮新元素索引
	childrenIndex = parentIndex
	// 获取上浮的下一轮父节点索引
	parentIndex = (childrenIndex - 1) / 2
}

// 堆调整完毕，将新元素的值插入新元素的正确索引位置
(*p)[childrenIndex] = temp }

// 删除元素时，下沉调整 func (p priorityQueue) downAdjust() { parentIndex := 0 endIndex := len(p) - 1 // 保存父节点的值，用于比较和最后的赋值，而不需要每一步都进行交换 temp := (p)[parentIndex] // 获取左孩子节点的索引，左孩子节点索引 = 2 * 父节点索引 + 1 childrenIndex := 2parentIndex + 1

// 当该父节点存在孩子（如果不存在孩子，则说明父节点是叶子节点，无需继续判断），则循环下沉判断并调整
for childrenIndex <= endIndex {
	// 如果父节点的值同时<=左右孩子的值，则说明符合小顶堆，调整结束
	if childrenIndex+1 <= endIndex && (*p)[childrenIndex+1].Val < (*p)[childrenIndex].Val {
		childrenIndex++
	}
	if temp.Val <= (*p)[childrenIndex].Val {
		break
	}
	// 将更小的那个孩子节点的值赋值到父节点中
	(*p)[parentIndex] = (*p)[childrenIndex]
	// 获取下沉的下一轮父节点索引
	parentIndex = childrenIndex
	// 获取下沉的下一轮左孩子节点索引
	childrenIndex = 2*parentIndex + 1
}

// 堆调整完毕，将父节点的值插入父节点的正确索引位置
(*p)[parentIndex] = temp } ```

  
func mergeKLists(lists []*ListNode) *ListNode {
    dummyHead := new(ListNode)
    tail := dummyHead
    pq := new(primaryQueue)
    // 将所有链表头节点加入小顶堆有序队列
    for i := 0; i < len(lists); i ++ {
        if lists[i] != nil {
            pq.Insert(lists[i])
        }
    }
    // 不断选取最小值结点加入结果链表，直到所有的有序链表遍历完
    for !pq.IsEmpty() {
        node := pq.Pop()
        tail.Next = node 
        tail = tail.Next
        if node.Next != nil {
            pq.Insert(node.Next)
        }
    }
    return dummyHead.Next
}

// 实现小顶堆优先级队列
type primaryQueue struct {
    heap []*ListNode
}

func (p *primaryQueue) swap(index1, index2 int) {
    p.heap[index1], p.heap[index2] = p.heap[index2], p.heap[index1]
}

func (p *primaryQueue) IsEmpty() bool {
    return len(p.heap) == 0 
}

// 插入新节点
func (p *primaryQueue) Insert(node *ListNode) {
    p.heap = append(p.heap, node)
    p.shitUp(len(p.heap) - 1) // 向上调整新插入节点
}

// 弹出最小值结点
func (p *primaryQueue) Pop() *ListNode {
    p.swap(0, len(p.heap) - 1)
    // pop node 
    node := p.heap[len(p.heap) - 1]
    p.heap = p.heap[:len(p.heap) - 1]
    // 向下调整交换后的第一个节点
    p.shitDown(0)
    return node 
}

// 如果父节点值比新插入节点值大则交换，调整为小顶堆，然后继续向上递归调整 // 上浮
func (p *primaryQueue) shitUp(index int) {
    if index > 0 {
        parent := (index - 1) /2 
        if p.heap[parent].Val > p.heap[index].Val {
            p.swap(parent, index)
            p.shitUp(parent)
        }
    }
}

// 向下调整当前节点为小顶堆，然后继续向下递归调整 // 下沉
func (p *primaryQueue) shitDown(index int) {
    left, right := 2*index +1, 2*index + 2 
    lesser := index
    if left < len(p.heap) && p.heap[left].Val < p.heap[lesser].Val {
		lesser = left
	}
	if right < len(p.heap) && p.heap[right].Val < p.heap[lesser].Val {
		lesser = right
	}
    if lesser != index {
        p.swap(lesser, index)
        p.shitDown(lesser)
    }
}

方法四：小顶堆简单写法

  
func mergeKLists(lists []*ListNode) *ListNode {
    if lists == nil || len(lists) == 0 {
        return nil
    }

    minHeap := []int{}
    for i := range lists {
        head := lists[i]
        for head != nil {
            minHeap = append(minHeap, head.Val)
            head = head.Next
        }
    }

    buildMinHeap(minHeap)

    dummyHead := new(ListNode)
    cur := dummyHead
    for len(minHeap) > 0 {
        cur.Next = &ListNode{Val: minHeap[0]}
        swap(minHeap, 0, len(minHeap)-1)
        minHeap = minHeap[:len(minHeap)-1]
        heapify(minHeap, 0)
        cur = cur.Next
    }

    return dummyHead.Next
}

func buildMinHeap(minHeap []int) {
    n := len(minHeap)
    for i := n/2-1; i >= 0; i-- {
        heapify(minHeap, i)
    }
}

func heapify(minHeap []int, i int) {
    n := len(minHeap)
    for {
        cur := i 
        left, right := 2*i+1, 2*i+2
        if left < n && minHeap[cur] > minHeap[left] {
            cur = left
        }
        if right < n && minHeap[cur] > minHeap[right] {
            cur = right
        }
        if i == cur { break }
        swap(minHeap, i, cur)
        i = cur
    }
}

func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

方法五：低效的堆排序实现

  
ype PriorityQueue struct {
	length   int
	max      int
	elements []*ListNode
}

func NewPriorityQueue(max int) *PriorityQueue {
	return &PriorityQueue{max: max}
}

func (pq *PriorityQueue) IsEmpty() bool {
	return pq.length == 0
}

func resort(array *[]*ListNode) {
	if len(*array) == 0 {
		return
	}
	currentElementIndex := len(*array) - 1

	for currentElementIndex > 0 {
		fatherElement := int((currentElementIndex - 1) / 2)
		innerIndex := currentElementIndex
		for (*array)[fatherElement].Val > (*array)[innerIndex].Val {
			exchange(array, innerIndex, fatherElement)
	
			innerIndex = fatherElement
			fatherElement = int((innerIndex - 1) / 2)
		}
		currentElementIndex -= 1
	}
}


func (pq *PriorityQueue) Add(n *ListNode) {
	pq.elements = append(pq.elements, n)
	pq.length += 1

	if pq.length == 1 {
		return
	}

	// re-sort
	resort(&pq.elements)
}

func (pq *PriorityQueue) Poll() *ListNode {
	// get min element from pq
	if pq.length < 1 {
		return nil
	}
    // re-sort
	resort(&pq.elements)
	pq.length -= 1
	minNode := pq.elements[0]


	pq.elements = pq.elements[1:]

	return minNode
}

func exchange(array *[]*ListNode, i int, j int) {
	tmp := (*array)[i]
	(*array)[i] = (*array)[j]
	(*array)[j] = tmp
}

func mergeKLists(lists []*ListNode) *ListNode {
	k := len(lists)

	dummy := &ListNode{Val: -1}
	p := dummy

	pq := NewPriorityQueue(k)

	for _, listnode := range lists {
        if listnode != nil {
            pq.Add(listnode)
        }
	}

	for !(pq.IsEmpty()) {
		minNode := pq.Poll()
		p.Next = minNode
		
		if minNode != nil && minNode.Next != nil {
			pq.Add(minNode.Next)
		}

		p = p.Next

	}
	return dummy.Next
}

快速排序

  
func mergeKLists(lists []*ListNode) *ListNode {
    // 清除掉链表数组中的空链表
    for i := 0; i < len(lists); i++ {
        if lists[i] == nil {
            lists = append(lists[0:i], lists[i+1:]...)
            i--
        }
    }
    // 如果链表数组被清除掉空链表后为空则直接返回 nil
    if len(lists) == 0 {
        return nil
    }

    node := new(ListNode)   // 合并中的链表游标
    head := node    // 合并后的链表头为 head.Next
    quickSort(&lists, 0, len(lists)-1)  // 先对链表数组根据各链表地一个元素进行排序
    for len(lists) > 1 {
        // 链表数组第一个元素始终是当前最小的元素
        node.Next = lists[0]
        node = node.Next
        lists[0] = lists[0].Next
        // 及时清理掉空链表
        if lists[0] == nil {
            lists = lists[1:]
            continue
        }
        // 使用二分法找到第一个链表的新位置，并重排链表保持有序
        index := findIndex(lists, lists[0].Val)
        temp := lists[0]
        copy(lists[:index], lists[1:index+1])
        lists[index] = temp
    }
    // 链表数组中剩余最后一个链表直接拼接在末尾
    if len(lists) == 1 {
        node.Next = lists[0]
    }

    return head.Next
}

func findIndex(lists []*ListNode, target int) int {
    l := 0
    r := len(lists)-1
    for l + 1 < r {
        mid := l - (l - r) / 2
        if lists[mid].Val < target {
            l = mid
        } else {
            r = mid
        }
    }
    // 注意这里的 <= 条件
    if lists[r].Val <= target {
        return r
    }
    return l
}

func quickSort(lists *[]*ListNode, begin, end int) {
    if begin >= end {
        return
    }
    l := begin
    r := end
    for l < r {
        for l < r && (*lists)[r].Val >= (*lists)[begin].Val {
            r--
        }
        for l < r && (*lists)[l].Val <= (*lists)[begin].Val {
            l++
        }
        (*lists)[l], (*lists)[r] = (*lists)[r], (*lists)[l]
    }
    (*lists)[begin], (*lists)[l] = (*lists)[l], (*lists)[begin]

    quickSort(lists, begin, l-1)
    quickSort(lists, l+1, end)
}

败者树

  
type ListNode struct {
	Val  int
	Next *ListNode
}

type loserTree struct {
	tree   []int
	leaves []*ListNode
}

var  dummyVal = 100000
var  dummyListNode = ListNode{Val: dummyVal}

func New(leaves []*ListNode) *loserTree {
	k := len(leaves)
	if k & 1 == 1  {
		leaves = append(leaves, &dummyListNode)
		k++
	}
	lt := &loserTree{
		tree:   make([]int, k),
		leaves: leaves,
	}
	if k > 0 {
		lt.initWinner(0)
	}
	return lt
}


func (lt *loserTree) initWinner(idx int) int {
	if idx == 0 {
		lt.tree[0] = lt.initWinner(1)
		return lt.tree[0]
	}
	if idx >= len(lt.tree) {
		return idx - len(lt.tree)
	}
	left := lt.initWinner(idx*2)
	right := lt.initWinner(idx*2+1)
	if lt.leaves[left] == nil {
		lt.leaves[left] = &dummyListNode
	}
	if lt.leaves[right] == nil {
		lt.leaves[right] = &dummyListNode
	}
	if lt.leaves[left].Val < lt.leaves[right].Val {
		left, right = right, left
	}
	lt.tree[idx] = left
	return right
}


func (lt *loserTree) Pop() *ListNode {
	if len(lt.tree) == 0 {
		return &dummyListNode
	}
	treeWinner := lt.tree[0]
	winner := lt.leaves[treeWinner]
	lt.leaves[treeWinner] = winner.Next
	if lt.leaves[treeWinner] == nil {
		lt.leaves[treeWinner] = &dummyListNode
	}
	treeIdx := (treeWinner + len(lt.tree)) / 2
	for treeIdx != 0 {
		treeLoser := lt.tree[treeIdx]
		if lt.leaves[treeLoser].Val  < lt.leaves[treeWinner].Val  {
			treeLoser, treeWinner  = treeWinner, treeLoser
		}
		lt.tree[treeIdx] = treeLoser
		treeIdx /= 2
	}
	lt.tree[0] = treeWinner
	return winner
}

func mergeKLists(lists []*ListNode) *ListNode {
	dummy := new(ListNode)
	pre := dummy
	lt := New(lists)
	for {
		node := lt.Pop()
		if node == &dummyListNode {
			break
		}
		pre.Next = node
		pre = node
	}
	return dummy.Next
}

值排序重建链表

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    head := new(ListNode)
    newHead := head
    // 最笨的方法
    nums := []int{}
    for i := 0; i < len(lists); i++ {
        for lists[i] != nil {
            nums = append(nums, lists[i].Val)
            lists[i] = lists[i].Next
        }
    }
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        node := &ListNode{Val: nums[i]}
        head.Next = node
        head = head.Next
    }
    return newHead.Next
}

基数排序

  
const (
    MAXSIZE = 20010
    OFFSET  = 10000
)

func mergeKLists(lists []*ListNode) *ListNode {
    cnt := make([]int, MAXSIZE)
    for i := 0; i < len(lists); i++ {
        for p := lists[i]; p != nil; p = p.Next {
            cnt[p.Val+OFFSET]++
        }
    }
    
    head := &ListNode{}
    for num := len(cnt)-1; num >= 0; num-- {
        for cnt[num] > 0 {
            s := &ListNode{Val: num-OFFSET, Next: head.Next}
            head.Next = s
            cnt[num]--
        }
    }
    
    return head.Next
}

分隔链表

题目要求

双链表头结点法：两个链表(有头结点)分别收集小于x的节点和大于等于x的节点，然后再连接两个链表

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    h1, h2 := &ListNode{}, &ListNode{}
    p1, p2 := h1, h2
    for  head != nil {
        if head.Val < x {
            p1.Next = head
            p1 = p1.Next
            head = head.Next
            continue
        }

        p2.Next = head
        p2 = p2.Next
        head = head.Next
    }

    p1.Next = h2.Next
    p2.Next = nil
    return h1.Next
}

双链表非头结点法：比“双链表头结点法”复杂且低效

  
func partition(head *ListNode, x int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    var h1, h2, p1, p2 *ListNode
    if head.Val < x {
        h1 = head
        p1 = h1
        head = head.Next

        for head != nil && head.Val < x {
            p1.Next = head
            p1 = p1.Next
            head = head.Next
        }

        if head != nil {
            h2 = head
            p2 = h2
            head = head.Next
        }
    } else {
        h2 = head
        p2 = h2
        head = head.Next

        for head != nil && head.Val >= x {
            p2.Next = head
            p2 = p2.Next
            head = head.Next
        }

        if head != nil {
            h1 = head
            p1 = h1
            head = head.Next            
        }        
    }

    for  head != nil {  
        if head.Val  < x {
            p1.Next = head
            p1 = p1.Next 
            head = head.Next    
            continue
        }

        p2.Next = head
        p2 = p2.Next
        head = head.Next
    }

    if p1 == nil {
        return h2
    }

    if p2 == nil {
        return h1
    }

    p1.Next = h2
    p2.Next = nil
    return h1
}

方法三：类似快排partition的原地交换

  
func partition(head *ListNode, x int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    prevHead := &ListNode{Next: head}

    par := prevHead
    prev, curr := head, head.Next
    for par.Next.Val < x && curr != nil {
        par = par.Next
        prev = prev.Next
        curr = curr.Next
    }

    for curr != nil {
        if curr.Val < x {
            prev.Next = curr.Next

            next := par.Next
            curr.Next = next
            par.Next = curr
            par = par.Next
            curr = prev.Next
        } else {
            prev, curr = prev.Next, curr.Next
        }
    }

    return prevHead.Next
}

链表的中间结点

找出链表的中间节点题目要求

两次遍历

一次遍历求出链表长度，第二次遍历得到对应节点

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    n := getListLength(head)
    half := n / 2
    for i := 0; i < half; i++ {
        head = head.Next
    }

    return head
}

func getListLength(head *ListNode) int {
    n := 0
    for head != nil {
        n++
        head = head.Next
    }

    return n
}

快慢双指针法

慢指针一次走一步，快指针一次走两步。快指针指向链尾时，慢指针也就到了中间节点。

  
func middleNode(head *ListNode) *ListNode {
	fastPointer := head
	slowPointer := head

	count := 0
	for {
		count++
		// 1次走1步
		if fastPointer.Next == nil {
			return slowPointer
		}
		fastPointer = fastPointer.Next

		// 2次走一步
		if count%2 == 1 {
			slowPointer = slowPointer.Next
		}
	}
}

  
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    if fast == nil || fast.Next == nil {
        return slow
    }

    return slow.Next
}

  
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    return slow
}

数组存储一次链表遍历结果

遍历链表时，把节点存入数组，利用数组的随机访问特性，直接找出中间节点

  
var arr = make([]*ListNode, 0, 100)
func middleNode(head *ListNode) *ListNode {
    arr = arr[0:0] 
    for head != nil {
        arr = append(arr, head)
        head = head.Next
    }

    return arr[len(arr)/2]
}

反转链表

题目要求

方法一

新建一个链表头节点，遍历原链表，使用头插法插入到新链表中即可。

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    rev, tmp := &ListNode{}, head

    for head != nil {
       tmp = head.Next
       head.Next = rev.Next
       rev.Next = head
       head = tmp 
    }

    return rev.Next
}

方法二

链表转化成数组，然后再按要求重新建立链接即可。

  
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    arr := []*ListNode{}
    for head != nil {
        arr = append(arr, head)
        head = head.Next
    }

    for i := len(arr)-1; i >= 1; i-- {
        arr[i].Next = arr[i-1]
    }

    arr[0].Next = nil
    return arr[len(arr)-1]
}

方法三

就地反转（先处理两个节点的反转，再传导到第三个节点）。就地逆置法和头插法的实现思想类似，但相对费解一些

  
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    p1, p2 := head, head.Next
    for p2 != nil {
        p1.Next = p2.Next
        p2.Next = head
        head = p2
        p2 = p1.Next
    }

    return head
}

方法四

迭代法：每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值

  
func reverseList(head *ListNode) *ListNode {
    var prev, next *ListNode

    for head != nil {
        next = head.Next
        head.Next = prev
        prev = head
        head = next
    }

    return prev
}

方法五

递归反转：

递归相当于函数参数的栈，通过 head.Next 遍历链表，直到 head.Next == nil
遍历的时候，会把 head.Next 压入栈中，通过 head = head.Next 使 head 的指向不断变化(从而实现遍历)
遍历完之后（newHead 成为最后一个节点，从函数的出口 if 可知），开始逐层退出，即出栈
递归函数前至递归函数所在行，属于压栈阶段
递归函数后至最后的return前，属于出栈阶段
全局变量是不会压栈的（这个地方特别注意）

  
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    //一直递归，找到链表中最后一个节点
    newHead := reverseList(head.Next)

    // 当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
    // 递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
    // 每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
    head.Next.Next = head
    head.Next = nil

    //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
    return newHead
}

栈是一段内存空间，用来存储数据，在函数的调用过程中存储什么呢？当一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需要完成3件事

将所有的实参、返回地址等信息传递给被调用函数保存(返回地址是指程序从函数返回时应该继续执行的地方)
为被调用函数的局部变量分配存储区
将控制转移到被调函数的入口

而被调用函数返回调用函数之前，系统也应完成3件事

保存被调函数的计算结果
释放被调函数的数据区
依照被调函数保存的返回地址将控制转移到调用函数

递归的压栈过程可以参看递归与栈的状态

反转链表II

头插法

找到left的前驱节点，记录left节点，以便连接right的后继节点
left-right之间的链表，类似于反转整个链表一样处理即可
把right原来的后继节点连到left之后即可

  
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == right {
        return head
    }
    
    ret := &ListNode{Next: head}
    p := ret
    for i := 1; i < left; i++ {
        p = p.Next
    }

    q := p.Next
    tail, tmp := q, q
    p.Next = nil
    for i := left; i <= right; i++ {
        tmp = q.Next
        q.Next = p.Next
        p.Next = q
        q = tmp
    }

    tail.Next = q
    return ret.Next
}

分段反转

分成三段：头节点->left前驱，left->right，right后继节点->链尾
反转left->right这整段链表
重新连接三段

  
func findPreNode(head *ListNode, n int) *ListNode {
    for i := 1; i < n; i++ {
        if head == nil {
            break
        }

        head = head.Next
    }

    return head
}

func reverseAll(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    h := &ListNode{}
    p, tmp := h, h
    for head != nil {
        tmp = head.Next
        head.Next = p.Next
        p.Next = head
        head = tmp
    }

    return h.Next
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == right {
        return head
    }

    list1 := &ListNode{Next: head}
    leftPre := findPreNode(list1, left)
    rightNode := findPreNode(leftPre.Next, right-left+1)
    list2, list3 := leftPre.Next, rightNode.Next
    rightNode.Next = nil

    leftPre.Next = reverseAll(list2)
    list2.Next = list3
    return list1.Next
}

  
func findNode(head *ListNode, n int) *ListNode {
    for i := 0; i < n; i++ {
        if head == nil {
            break
        }

        head = head.Next
    }

    return head
}

func reverseAll(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    h := &ListNode{}
    p, tmp := h, h
    for head != nil {
        tmp = head.Next
        head.Next = p.Next
        p.Next = head
        head = tmp
    }

    return h.Next
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == right {
        return head
    }

    list1 := &ListNode{Next: head}
    leftPre := findNode(list1, left-1)
    rightNode := findNode(leftPre, right-left+1)
    list2, list3 := leftPre.Next, rightNode.Next
    rightNode.Next = nil

    leftPre.Next = reverseAll(list2)
    list2.Next = list3
    return list1.Next
}

递归

关键是要找到数学上的递归映射，即转化为自问题(规模不断减小，但问题性质不变)

  
var flag *ListNode
func reverseRight(head *ListNode, r int) *ListNode{
    if r == 1 {//当到达最后一个节点的时候
        flag = head.Next//记录当前节点的下一个节点，她需要成为翻转后的部分的尾节点的Next
		return head
    }
		
    last := reverseRight(head.Next, r-1)//翻转后可以得到新的头节点
    head.Next.Next = head//把头节点变成反转部分的尾节点
    head.Next = flag//尾节点的next是未反转部分的头节点
    return last//返回头节点
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || head.Next == nil || left == right {
		return head
	}

    if left == 1 {//left为1的时候相当于反转前right个节点
        return reverseRight(head, right)
    }

    // 前进到left处触发base 
    head.Next = reverseBetween(head.Next, left-1, right-1)
    return head
}

  
func reverseBetween(head *ListNode, m int, n int) *ListNode {
	if head == nil || head.Next == nil || m == n {
		return head
	}

	if n == 1 {
		return head
	}

	nextNode := head.Next
	ptr := reverseBetween(nextNode, m-1, n-1)
	if m > 1 {
		head.Next = ptr
		return head
	}

	head.Next = nextNode.Next
	nextNode.Next = head
	return ptr
}

  
func reverseBetween(head *ListNode, left, right int) *ListNode {
    var dfs func(*ListNode,int,int,*ListNode)*ListNode
    dfs=func(node *ListNode,left,right int,result *ListNode)*ListNode{
        switch {
            case node==nil:
                return result
            case left>1:
                return &ListNode{node.Val,dfs(node.Next,left-1,right-1,result)}
            case right>=1:
                return dfs(node.Next,left,right-1,&ListNode{node.Val,result})
            case result!=nil:
                return &ListNode{result.Val,dfs(node,left,right,result.Next)}
            default:
                return &ListNode{node.Val,dfs(node.Next,left,right,result)}
        }
    }
		
    return dfs(head,left,right,nil)
}

值反转拷贝

找到待反转区间
用数组暂存该区间的值
数组反转后赋值给链表区间

  
func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || head.Next == nil || m == n {
        return head
    }

    start := findReverseStartPoint(head, m)
    arr := getReverseListValues(start, n-m+1)
    reverseValue(start, arr)

    return head
}

func findReverseStartPoint(head *ListNode, m int) *ListNode {
	for head != nil && m > 1 {
        head = head.Next
        m--		
	}

    return head
}

func getReverseListValues(head *ListNode, m int) []int {
    ret := make([]int, m)
    for i := 0; i < m; i++ {
        ret[i] = head.Val
        head = head.Next
    }

    return ret
}

func reverseValue(start *ListNode, data []int) {
    for i := len(data)-1; i >= 0; i-- {
        start.Val = data[i]
        start = start.Next
    }
}

leetCode 题解

刷题正确打开方式

算法思想

链表

判断链表是否存在环

标记法

快慢双指针法

链表有环则找出线与环的交接点

标记法

快慢双指针法

找出相交单链表的交点

方法一

方法二

方法三

方法四

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

方法一

方法二

方法三

方法四

合并两个有序链表

哨兵迭代法

递归法

合并K个有序链表

逐一两两合并

分治递归法(归并排序)

K指针

优先队列(二叉堆)

快速排序

败者树

值排序重建链表

基数排序

分隔链表

链表的中间结点

两次遍历

快慢双指针法

数组存储一次链表遍历结果

反转链表

方法一

方法二

方法三

方法四

方法五

反转链表II

头插法

分段反转

递归

值反转拷贝

我要评论

相关文章

算法基石

数据结构基础

nacos杂谈