算法 - (链表)

2020-10-17 3049 words 7 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.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.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.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
}