双指针

876-链表的中间结点

解题思路：

• 快慢指针：快指针走两步，慢指针走一步，fast走完slow就是中点 注意事项：
• 当链表长度是偶数（两个中点），slow会指向后一个中点

func middleNode(head *ListNode) *ListNode {
    // 创建快慢指针,快指针走两步，慢指针走一步
    slow, fast := head, head

    for fast != nil && fast.Next != nil {

        slow = slow.Next

        fast = fast.Next.Next

    }
    return slow
}

bm6-判断链表中是否有环

解题思路：

• 快慢指针：快指针走两步，慢指针走一步
• 判断成环：快指针能走到结尾（快慢指针没有遇到）则不成环，反之成环

func hasCycle(head *ListNode) bool {

    slow, fast := head, head

    for fast != nil && fast.Next != nil {

        slow = slow.Next

        fast = fast.Next.Next

        if slow == fast {
            return true
        }
    }
    return false
}

142-环形链表Ⅱ

解题思路：

• 快慢指针：快指针走两步，慢指针走一步
• 环起点：当快慢指针相遇时，让其中一个指针指向头节点，然后以相同的速度前进，再次遇到就是环开始的位置

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			break
		}
	}

	// fast走完判断fast节点是否为空（空则不成环）
	if fast == nil || fast.Next == nil {
		return nil
	}

	slow = head

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

	return fast
}

160-相交链表

解题思路： p1,p2两个指针以相同步长分别遍历list1和list2，当遍历到链表结尾时继续遍历对方的链表，若p1,p2相遇，则该点时是相交点

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	p1, p2 := headA, headB

	for p1 != p2 {
		if p1 == nil {
			p1 = headB
		} else {
			p1 = p1.Next
		}

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

	return p1
}

21-合并两个有序链表

描述： 将两个升序链表合并为一个新的 升序 链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。 解题思路： 使用双指针同时遍历两个链表，比较两个链表的大小并将较大/小值插入虚拟头节点中 注意： 使用虚拟头节点可以减少头节点判空操作，简化代码

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	// 1. 创建虚拟头节点
	dummpy := &ListNode{}
	p := dummpy
	// 2. 将list1，list2分别赋值给p1，p2指针
	p1, p2 := list1, list2
	// 3. 利用p1，p2同时遍历两个链表并比较大小,将较小的节点插入虚拟头节点
	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
	}
	// 5. 将剩余的有序列表插入已排序链表
	if p1 != nil {
		p.Next = p1
	}

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

	// 6. 返回排序后的链表
	return dummpy.Next
}

86-分隔链表

描述： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 注意： 使用虚拟头节点可以减少头节点判空操作，简化代码

func partition(head *ListNode, x int) *ListNode {
	// 1.构建两个虚拟头节点分别用来存放大于/小于x的节点
	dummpy1 := &ListNode{}
	dummpy2 := &ListNode{}

	p := head

	p1, p2 := dummpy1, dummpy2

	// 2.遍历链表并把节点值与x进行比较，并插入两个虚拟节点
	for p != nil {
		if p.Val >= x {
			p2.Next = p
			p2 = p2.Next
		} else {
			p1.Next = p
			p1 = p1.Next
		}

		// 为了防止测试数据中存在环形链表，要先拆分再往下走
		temp := p.Next
		p.Next = nil
		p = temp
	}

	// 3. 连接两个虚拟链表并返回
	p1.Next = dummpy2.Next

	return dummpy1.Next
}