算法-链表

1. 双指针技巧

1.1 反转链表🔥

• 循环版本

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func ReverseList(head *ListNode) *ListNode {
	var prev, next *ListNode // 1. 三个辅助指针，前后和当前
	curr := head             // 2. 当前指针指向头结点，循环判断
	for curr != nil {
		next = curr.Next // 3. 先给后面的指针赋值，四连咬
		curr.Next = prev
		prev = curr
		curr = next
	}

	return prev
}

func main() {
	List1 := BuildList()
	fmt.Println("old", GetList(List1))
	List2 := ReverseList(List1)
	fmt.Println("new", GetList(List2))
}

func BuildList() *ListNode {
	L3 := &ListNode{Val: 3}
	L2 := &ListNode{Val: 2, Next: L3}
	L1 := &ListNode{Val: 1, Next: L2}
	return L1
}

func GetList(head *ListNode) []int {
	var arr []int
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	return arr
}

头脑风暴

1. 搞三个临时指针，前后和当前。
2. 当前=头指针，循环判断。
3. 先暂存next，然后四连咬。
4. 返回 prev。

// 1->2->3->nil

// 1->nil  			 | 2->3->nil
// 2->1->nil		 | 3->nil
// 3->2->1->nil  |  nil

• 递归版本（返回最后的指针）（原地改两个指向）

// 1->2->3->nil

/// head=3
// return

/// head=2
// 3->2
// 2->nil

/// head=1
// 2->1
// 1->nil

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

	last := ReverseList(head.Next)
	head.Next.Next = head
	head.Next = nil

	return last
}

1.2 合并链表

• https://leetcode.cn/problems/merge-two-sorted-lists/

• l1, l2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    p1 := list1 
    p2 := list2
    p := &ListNode{}
    dummy := p

    for p1 !=nil && p2 !=nil{
        if p1.Val > p2.Val{
            p.Next = p2
            p2 = p2.Next
        }else{
            p.Next = p1
            p1 = p1.Next
        }
        p = p.Next
    }

    if p1 != nil {
        p.Next = p1
    }
    if p2 != nil {
        p.Next = p2
    }
    
    return dummy.Next
}

1.3 判断链表有环

• https://leetcode.cn/problems/linked-list-cycle/
• 相交点不是有环的那个点

func hasCycle(head *ListNode) bool {
    slow := head
    fast := head
    for (fast != nil && fast.Next != nil){  // 一定要判断 fast
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast{
            return true
        }
    }
    return false
}

如果有环，返回环的节点

• https://leetcode.cn/problems/linked-list-cycle-ii/

func detectCycle(head *ListNode) *ListNode {
    slow := head
    fast := head
    cycle := false
    for (fast != nil && fast.Next != nil){ 
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast{
            cycle = true
            break
        }
    }
    if !cycle{
        return nil
    }

    p1 := head
    p2 := slow // 或者 fast
    for p1 != p2 {
        p1 = p1.Next
        p2 = p2.Next
    }
    return p1
}

1.4 分割链表

• https://leetcode.cn/problems/partition-list/description/
• 多用临时指针，先放到两个链表上，最后再接上。

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func BuildList() *ListNode {
	L1 := &ListNode{Val: 1}
	L2 := &ListNode{Val: 4}
	L3 := &ListNode{Val: 3}
	L4 := &ListNode{Val: 2}
	L5 := &ListNode{Val: 5}
	L6 := &ListNode{Val: 2}
	L1.Next = L2
	L2.Next = L3
	L3.Next = L4
	L4.Next = L5
	L5.Next = L6
	return L1
}
func GetList(head *ListNode) []int {
	var arr []int
	for head != nil {
		arr = append(arr, head.Val)
		head = head.Next
	}
	return arr
}

func partition(head *ListNode, x int) *ListNode {
	dummy1 := &ListNode{} // 小于x
	dummy2 := &ListNode{} // 大于x
	p1 := dummy1          // 小于x
	p2 := dummy2          // 大于x

	p := head
	for p != nil {
		if p.Val < x {
			p1.Next = p
			p1 = p1.Next
		} else {
			p2.Next = p
			p2 = p2.Next
		}

		// 把原始链表整断
		tmp := p.Next
		p.Next = nil
		p = tmp
	}
	
  // 接上链表
	p1.Next = dummy2.Next
	return dummy1.Next
}

func main() {
	head := BuildList()
	fmt.Println("origin", GetList(head))
	partitionList := partition(head, 3)
	fmt.Println("partition", GetList(partitionList))
}

1.5 链表是否相交

• https://leetcode.cn/problems/intersection-of-two-linked-lists/

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pos1 := headA
    pos2 := headB
    for pos1 != pos2 {
        if pos1 != nil{
            pos1 = pos1.Next
        }else{
            pos1 = headB
        }

        if pos2 != nil {
            pos2 = pos2.Next
        }else{
            pos2 = headA
        }
    }
    return pos2
}

1.6 倒数第K个节点

• https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

• 先让快指针走k步，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。

func getKthFromEnd(head *ListNode, k int) *ListNode {
    fast := head
    slow := head
    for k >0 && fast != nil {
        fast = fast.Next
        k--
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

2. 其他

2.1 两两交换链表中的节点(中等)

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

    next := head.Next  
    ok := swapPairs(head.Next.Next)
    head.Next.Next = head
    head.Next = ok

    return next
}

2.2 删除链表的节点(简单)

func deleteNode(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    head.Next = deleteNode(head.Next, val)
    if head.Val == val {
        return head.Next
    }else{
        return head
    }
}

2.3 从尾到头打印链表(简单)

func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }

    res := append(reversePrint(head.Next), head.Val) 
    return res
}