part2

24.两两交换链表中的节点

分析

1. 设置虚拟头结点，虚拟头结点的下一个是头结点
2. 虚拟头结点的下一个为头结点的下一个
3. 头结点的下一个为脖节点的下一个
4. 虚拟头结点的下一个结点的下一结点设置为头结

代码

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

	for cur.Next != nil && cur.Next.Next != nil {
		first := cur.Next
		second := cur.Next.Next
		first.Next = second.Next
		cur.Next = second
		second.Next = first
		cur = first
	}
	return dum.Next
}

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

分析

1. 双指针
2. 见代码行间注释

代码

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// 创建一个虚拟头节点
	dummy := &ListNode{Next: head}
	// 初始化快慢指针，都指向虚拟头节点
	s, f := dummy, dummy
	// 先让快指针 f 前进 n 步
	for n > 0 && f.Next != nil {
		f = f.Next
		n--
	}

	// 快指针再前进一步，使得快慢指针之间的距离为 n+1
	// 这样当快指针到达链表末尾时，慢指针正好指向倒数第 n+1 个节点
	f = f.Next

	// 快慢指针同时前进，直到快指针到达链表末尾
	for f != nil {
		s = s.Next
		f = f.Next
	}

	// 此时慢指针 s 指向倒数第 n+1 个节点
	// 删除倒数第 n 个节点（即 s.Next）
	s.Next = s.Next.Next
	// 返回真正的头节点
	return dummy.Next
}

面试题 02.07. 链表相交

分析

1. 相遇法，走过你来时的路
2. 差值双指针
3. 哈希映射法

代码

// 相遇法
// 4 0 5 1 2 8
// 3 1 2 8

// 4 0 5 1 2 8 3 1 2 8
// 3 1 2 8 4 0 5 1 2 8
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	l1, l2 := headA, headB
	for l1 != l2 {
		if l1 != nil {
			l1 = l1.Next
		} else {
			l1 = headB
		}

		if l2 != nil {
			l2 = l2.Next
		} else {
			l2 = headA
		}
	}
	return l1
}

// 哈希映射
func getIntersectionNode1(headA, headB *ListNode) *ListNode {
	// 创建一个哈希集合，用于存储链表A中的所有节点
	nodeSet := make(map[*ListNode]bool)
	
	// 将链表A中的所有节点加入哈希集合
	curA := headA
	for curA != nil {
		nodeSet[curA] = true
		curA = curA.Next
	}
	
	// 遍历链表B，检查节点是否在哈希集合中
	curB := headB
	for curB != nil {
		if nodeSet[curB] {
			return curB // 找到相交节点
		}
		curB = curB.Next
	}
	
	return nil // 没有相交节点
}

// 双指针差值法
func getIntersectionNode2(headA, headB *ListNode) *ListNode {
	// 计算两个链表的长度
	lenA, lenB := 0, 0
	curA, curB := headA, headB
	
	for curA != nil {
		lenA++
		curA = curA.Next
	}
	
	for curB != nil {
		lenB++
		curB = curB.Next
	}
	
	// 让较长的链表先走差值步
	curA, curB = headA, headB
	if lenA > lenB {
		for i := 0; i < lenA-lenB; i++ {
			curA = curA.Next
		}
	} else {
		for i := 0; i < lenB-lenA; i++ {
			curB = curB.Next
		}
	}
	
	// 同时遍历两个链表，直到找到相交节点
	for curA != curB {
		curA = curA.Next
		curB = curB.Next
	}
	
	return curA // 如果没有相交，curA和curB最终都为nil
}

142.环形链表 II

分析

1. 见代码分析
2. 数学题

代码

func detectCycle(head *ListNode) *ListNode {
	// 处理空链表或只有一个节点的情况
	if head == nil || head.Next == nil {
		return nil
	}

	// 初始化快慢指针
	s, f := head, head

	// 第一阶段：检测是否有环
	for f != nil && f.Next != nil {
		// 先移动指针
		s = s.Next
		f = f.Next.Next

		// 然后检查是否相遇
		if s == f {
			// 找到环，进入第二阶段
			// 重置一个指针到链表头
			p := head
			// 两个指针以相同速度移动，相遇点即为环的入口
			for p != s {
				p = p.Next
				s = s.Next
			}
			return p
		}
	}

	// 没有环
	return nil
}

总结

1. 双指针
2. 模拟行为
3. 哈希表
4. 数学思维