算法 - (链表)

2020-10-17 4106 words 9 minutes

Contents

Warning

本文最后更新于 July 31, 2022，文中内容可能已过时，请谨慎使用。

数组、链表是编程语言中最常见的数据结构，也是最基础的数据结构。以下会以几道 LeetCode 巩固自己的基础

链表

// 定义单链表
type ListNode struct {     
	Val 	int
	Next 	*ListNode
}

func (ln *ListNode) add(v int) {
	if ln == nil {
		ln = &ListNode{Val: v,Next: nil}
	}
	for ln.Next != nil {
		ln = ln.Next
	}
	ln.Next = &ListNode{Val: v,Next: nil}
}

func (ln *ListNode) traverse() {
	for ln != nil {
		fmt.Printf("%d ",ln.Val)
		ln = ln.Next
	}
}

LeetCode

No.2 两数相加

链接：https://leetcode.cn/problems/add-two-numbers/description/
思路：

func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {
    var tail *ListNode
    carry := 0
    for l1 != nil || l2 != nil {
        n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10
        if head == nil {
            head = &ListNode{Val: sum}
            tail = head
        } else {
            tail.Next = &ListNode{Val: sum}
            tail = tail.Next
        }
    }
    if carry > 0 {
        tail.Next = &ListNode{Val: carry}
    }
    return
}

No.19 删除链表的倒数第N个节点

链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
思路：最常见且高效的方法是使用双指针法。这种方法只需要一次遍历即可完成任务，避免了两次遍历的开销。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

package main

// ListNode 定义了链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 创建一个虚拟头节点
    dummy := &ListNode{Val: 0, Next: head}
    
    // 初始化快慢指针
    fast := dummy
    slow := dummy
    
    // 快指针先行 n+1 步
    for i := 0; i <= n; i++ {
        if fast == nil {
            // 如果链表长度小于等于n，直接返回nil
            return nil
        }
        fast = fast.Next
    }
    
    // 快慢指针同时移动，直到快指针到达链表末尾
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    // 此时慢指针slow位于要删除节点的前一个节点
    // 删除目标节点
    slow.Next = slow.Next.Next
    
    // 返回虚拟头节点的下一个节点，即新的链表头
    return dummy.Next
}

No.21 合并两个链表

链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/
思路1: 迭代法

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	tmp := &ListNode{}

	prev := tmp
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val{
			prev.Next = l1
			prev = prev.Next

			l1 = l1.Next
		}else {
			prev.Next = l2
			prev = prev.Next

			l2 = l2.Next
		}
	}

	if l2 != nil {
		prev.Next = l2
	}

	if l1 != nil {
		prev.Next = l1
	}

	return tmp.Next
}

No.22 链表的倒数第k个节点

链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
思路1：将节点全部保存到列表里，再返回索引，当然这个方法费空间。思路2：快慢指针。即 fast、slow 两个指针，fast 先移动k步，再slow和fast一起移动，当fast遍历结束时，slow就是倒数第k步。

// 非常low的写法
func getKthFromEnd(head *ListNode, k int) *ListNode {
	var rest []*ListNode
	for node := head; node != nil; node = node.Next {
		rest = append(rest, node)
	}
	if len(rest) >= k {
		return rest[len(rest) - k]
	}
	return nil
}

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

No.23 合并K个有序链表

链接：https://leetcode.cn/problems/merge-k-sorted-lists/
思路：分治法 (Divide and Conquer) 这种方法类似于归并排序。我们可以将链表数组不断地对半分割，直到每个子问题都只包含一个或零个链表。然后，我们递归地将这些子链表两两合并。

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

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

func merge(lists []*ListNode, left, right int) *ListNode {
    if left == right {
        return lists[left]
    }
    mid := left + (right-left)/2
    l1 := merge(lists, left, mid)
    l2 := merge(lists, mid+1, right)
    return mergeTwoLists(l1, l2)
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    } else {
        l2.Next = mergeTwoLists(l1, l2.Next)
        return l2
    }
}

No.25 K个一组翻转链表

链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
思路：其实很简单，只要会链表翻转就会K个一组翻转。写一个翻转函数，将头部K个翻转，K个后面的再拼回来。循环此过程

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil || k <= 1 {
		return head
	}

	dummy := &ListNode{}
	moved := dummy

	for head != nil {
		// head next
		tail := head
		for i := 0; i < k && tail != nil; i++ {
			tail = tail.Next
		}
		if tail == nil {
			break
		}

		// 记录下一组的起始节点
		nextGroup := tail.Next

		newHead, newTail := reverseKNode(head, k)
		moved.Next = newHead
		newTail.Next = nextGroup
		moved = newTail
		
		head = nextGroup
	}

	return dummy.Next
}

func reverseKNode(head *ListNode, k int) (*ListNode, *ListNode) {
	var prev *ListNode = nil
	var cur *ListNode = head

	for i := 0; i < k && cur != nil; i++ {
		next := cur.Next
		cur.Next = prev
		prev = cur
		cur = next
	}

	// head 是原先的链表头，反转后，是链表的尾部
	return prev, head
}

No.83 删除排序链表重复项

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
思路1：题解感觉和我差不太多，我的思路是先把重复项移到尾端，然后cur 指针指向重复项的尾端就好了。但不知道为啥 8ms 打败 7.3% 。理论就是 O(N) 啊。

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

	newHead := head
	moved := newHead

	for head != nil {
		// 找到下一个不同值的节点
		for head.Next != nil && head.Val == head.Next.Val {
			head = head.Next
		}
		// 连接不重复的节点
		moved.Next = head.Next
		moved = moved.Next
		head = head.Next
	}

	return newHead
}

No.92 翻转局部链表

链接：https://leetcode.cn/problems/reverse-linked-list-ii/description/
思路：取前半部分，再写一个链表翻转的函数，最后将后半部分接上。这里可以把链表翻转抽象出来。

func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil {
		return nil
	}
	length := right - left
	tmp := &ListNode{}
	tmp.Next = head
	cur := tmp

    // 将指针移动到翻转的前半部分
	for head != nil && left - 1 > 0 {
		next := head.Next

		cur.Next = head
		cur = cur.Next

		head = next
		left --
	}
    
	next := head
	cur.Next = reverseList(next, length+1)

	return tmp.Next
}

// 生成翻转和翻转的后半部分 
func reverseList(head *ListNode, length int) *ListNode {
if head == nil || length <= 0 {
		return head
	}

	var prev *ListNode = nil
	var cur *ListNode = prev

	for head != nil && length > 0 {
		next := head.Next

		head.Next = prev
		cur = head
		prev = cur

		length --
		head = next
	}
	next := head

	tmp := cur
	for tmp.Next != nil {
		tmp = tmp.Next
	}
	tmp.Next = next

	return cur
}

思路二：简单的看，将列表拆成3部分，第一部分是0-left，不需要反转，第二部分是 left-right 需要反转，right 之后的部分。

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	group := &ListNode{}
	groupMoved := group
    
    // 获取 0-left 部分,group1 是前半部分，newHead 是后半部分
	group1, newHead := getListByIndex(head, left-1)
	head = newHead

	groupMoved.Next = group1
	for groupMoved.Next != nil { // 指针前进
		groupMoved = groupMoved.Next
	}

    // 获取 left-right 部分
	group2, newHead := getListByIndex(head, right-left+1)

	reverseGroup := reverse(group2)
	groupMoved.Next = reverseGroup
	for groupMoved.Next != nil {  // 指针前进
		groupMoved = groupMoved.Next
	}
	groupMoved.Next = newHead

	return group.Next
}

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

	// 获取前N个节点
	front := head
	current := head
	for i := 1; i < k && current != nil; i++ {
		current = current.Next
	}

	// 如果不足N个节点
	if current == nil {
		return head, nil
	}

	// 分割链表
	back := current.Next
	current.Next = nil // 断开连接

	return front, back
}

// 反转函数
func reverse(head *ListNode) *ListNode {
	var tail *ListNode
	moved := tail

	for head != nil {
		next := head.Next
		movedNext := moved
		moved = head
		moved.Next = movedNext
		head = next
	}

	return moved
}

No.141 环形链表

链接: https://leetcode-cn.com/problems/linked-list-cycle/
思路1：这道题思路非常简单，就是快慢指针，慢指针每次前进一步，快指针每次前进两步。如果存在环快指针一定会追上慢指针，问题就是边界条件太多，需要仔细判断。
思路2：hash表存已有的数据做对比，这个最简单，不演示啦~

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

	return false
}

No.142 环形链表 II

链接：https://leetcode.cn/problems/linked-list-cycle-ii/
思路: 快慢指针

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

package main

// ListNode 定义了链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
    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
        
        // 如果快慢指针相遇，说明有环
        if slow == fast {
            // 步骤二：找到环的入口
            ptr := head
            for ptr != slow {
                ptr = ptr.Next
                slow = slow.Next
            }
            return ptr // ptr 和 slow 在环的入口处相遇
        }
    }
    
    // 如果循环结束，fast 到达 nil，说明没有环
    return nil
}

No.148 排序链表

链接：https://leetcode.cn/problems/sort-list/
思路：这道题采用归并排序的方法，将链表拆成足够小的部分，然后排序，就相当于是有序链表的合并，而拆到足够细时，因为链表就一个值，所以当然是有序的

func sortList(head *ListNode) *ListNode {
	return sort(head, nil)
}

func sort(head *ListNode, tail *ListNode) *ListNode {
	if head == nil {
		return nil
	}

    // 拆到足够细了，就是链表的一个节点
	if head.Next == tail {
		head.Next = nil
		return head
	}

	fast := head
	slow := head

	for fast.Next != tail {
		fast = fast.Next
		slow = slow.Next
		if fast.Next != tail {
			fast = fast.Next
		}
	}
	return merge(sort(head, slow), sort(slow, tail))
}

// 有序链表的合并
func merge(p, q *ListNode) *ListNode {
	if p == nil {
		return q
	}
	if q == nil {
		return p
	}

	tmp := &ListNode{}
	cur := tmp
	for p != nil && q != nil {
		if p.Val > q.Val {
			cur.Next = &ListNode{Val: q.Val, Next: nil}
            q = q.Next
		} else {
			cur.Next = &ListNode{Val: p.Val, Next: nil}
			p = p.Next
		}
		cur = cur.Next
	}

	if p != nil {
		cur.Next = p
	} else {
		cur.Next = q
	}

	return tmp.Next
}

No.160 相交链表

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/
思路：可以直接将所有节点存到 hash 表中。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	tmp := make(map[*ListNode]struct{})
	for headA != nil {
		tmp[headA] = struct{}{}
		headA = headA.Next
	}
	for headB != nil {
		if _, ok := tmp[headB]; ok {
			return headB
		}
		headB = headB.Next
	}
	return nil 
}

##No.203 移除链表元素

链接：https://leetcode.cn/problems/remove-linked-list-elements/
思路：很简单呐，就是双循环，里面那层循环遇到相等的就往后移动

func removeElements(head *ListNode, val int) *ListNode {
	if head == nil {
		return nil 
	}
	
	tmp := &ListNode{}
	prev := tmp
	
	for head != nil {
		for head != nil && head.Val == val {
			head = head.Next
		}
		prev.Next = head
		prev = prev.Next
		if head != nil {
			head = head.Next
		}
	}
	
	return tmp.Next
}

或者可以这么写, 思维逻辑清晰，不过追加这块是一直在创建新的Node，不是复用Head的

func removeElements(head *ListNode, val int) *ListNode {
	tmp := &ListNode{}
	moved := tmp
	for head != nil {
		if head.Val != val {
			moved.Next = &ListNode{Val: head.Val}
			moved = moved.Next
		}
		head = head.Next
	}

	return tmp.Next
}

No.206 反转链表

链接：https://leetcode-cn.com/problems/reverse-linked-list/
思路1：双指针本质还是遍历 head，上面的next := head.Next和下面的head = next 就是为了遍历，中间的三行是当前head的节点的下一个指向之前，cur即为当前head节点，cur 成为历史 prev

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

	var prev *ListNode = nil
	cur := prev

	for head != nil {
		next := head.Next  // 存下一个

		head.Next = prev // haed 的Next指向 prev
		cur = head       // cur 就是 head
		prev = cur		 // cur 成为 prev

		head = next   // head 前进
	}

	return cur
}

或者这么写，其实逻辑也很清晰

func reverseList(head *ListNode) *ListNode {
	var tail *ListNode = nil
	for head != nil {
		next := head.Next
		nextTail := tail
		tail = head
		tail.Next = nextTail
		head = next
	}
	return tail
}

No.234 回文链表

链接：https://leetcode.cn/problems/palindrome-linked-list/
思路：这道题很奇怪，就是遍历链表，赋值到数组中，再循环判断。

func isPalindrome(head *ListNode) bool {
var vals []int
	for ; head != nil; head = head.Next {
		vals = append(vals, head.Val)
	}
	n := len(vals)
	for i, v := range vals[:n/2] {
		if v != vals[n-1-i] {
			return false
		}
	}
	return true
}