链表
24. 两两交换链表中的节点
看完题目的第一想法
两两交换链表中的节点其实就是改变链表节点之间的指针
- 将第二个节点的Next指针指向第一个节点
- 第一个节点的指针指向第三个节点，后面依次重复此操作，
- 那么就可以使用递归来求解：
- 设递归函数是
swapPairs(head *ListNode) *ListNode此函数能够两两交换链表中的指针 - 返回值是第2个节点
- 递归的结束条件是交换的链表不足2个节点。
- 设递归函数是
package main
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
node1 := head
node2 := node1.Next
node3 := node2.Next
node2.Next = node1
node1.Next = swapPairs(node3)
return node2
}
使用迭代的方式
可以使用迭代的方式来求解，为了保证代码处理的一致性，引入了虚拟头结点。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapPairs(head *ListNode) *ListNode {
dummyHead := &ListNode{Next: head}
cur := dummyHead
for cur.Next != nil && cur.Next.Next != nil {
// 记录第1个节点
tmp := cur.Next
// 记录第3个节点
tmp1 := cur.Next.Next.Next
// 将虚拟头结点指向第2个节点
cur.Next = cur.Next.Next
// 将第2个节点指向第1个节点
cur.Next.Next = tmp
// 将第1个节点指向第3个节点
cur.Next.Next.Next = tmp1
// cur移动2位
cur = cur.Next.Next
}
return dummyHead.Next
}
今日收获
- 使用递归的方式代码比较简洁
- 使用迭代的方式逻辑比较清晰，使用虚拟头结点可以简化编码难度
注意：移动指针之前需要暂存第1个和第3个节点，防止因为改变指针的指向导致节点丢失
19. 删除链表的倒数第 N 个结点
看完题目的第一想法
删除倒数第N个结点，直接就可以想到双指针
- 定义2个指针分别为
fast和slow - 让
fast先走N步之后两个指针同时向后走 - 当
fast指针走到尾部时，slow所指向的就是删除的元素
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{Next: head}
slow := dummy
fast := dummy
for i := n; i > 0; i-- {
fast = fast.Next
}
// 让fast多走一步，这样slow就可以指向删除元素的前一个元素
fast = fast.Next
for fast != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
今日收获
删除倒数第N个结点使用双指针的解法，有一个技巧就是让fast指针多走一步，这样slow就指向了删除元素的上一个元素，通过slow.Next=slow.Next.Next操作即可。
使用虚拟头结点方便处理删除实际头结点的逻辑。
面试题 02.07. 链表相交
思路
题目数据保证整个链式结构中不存在环，可以将为null的结点看做是一个特殊的结点，这样两个不存在环的链表一定是相交的。
设链表A长度为a, 链表B长度为b, 相交链表长度为c，则\(a + c + b = b + c + a\)。当两个链表相交于null，即无相交时有\(a+b=b+a\)。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a := headA
b := headB
// 当a==b==null时 结束循环
for a != b {
if a == nil {
a = headB
} else {
a = a.Next
}
if b == nil {
b = headA
} else {
b = b.Next
}
}
return a
}
随想录的思路
定义两个变量curA、curB,分别指向headA、headB, 当两个链表不相等时，让长度长的链表的头指针先移动gap（2个链表长度的差值）的长度。
假设lenA大于lenB,那么curA先移动gap，此时curA与curB是尾对其的，此时就可以比较curA与curB是否相等，如果不相等继续往下走，直到为null。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
curA, curB := headA, headB
lenA, lenB := 0, 0
for curA != nil {
lenA++
curA = curA.Next
}
for curB != nil {
lenB++
curB = curB.Next
}
curA = headA
curB = headB
if lenA < lenB {
curA, curB = curB, curA
lenA, lenB = lenB, lenA
}
gap := lenA - lenB
for gap > 0 {
curA = curA.Next
gap--
}
for curA != curB {
curA = curA.Next
curB = curB.Next
}
return curA
}
今日收获
- 两个不存在环的链表一定会相交于一点（这个点可以是null），因此可以利用这一特性当headA为空时，将headA指向到headB，继续遍历； 当headB为空时，将headB指向到headA，继续遍历；遍历完len(headA)+len(headB)长度时一定会有相交的点。
- 利用长度差，因为相交的点一定是出现在短的链表中的。将 headA 与 headB 尾对其，开始遍历比较出现相等的点即相交的点。
142. 环形链表 II
思路
- 使用快慢指针可以检测链表是否有环
快指针每次走2步，慢指针每次走1步，如果快指针为空那么一定没有环；
如果快指针等于慢指针了说明在环内相遇； - 设链表头到环的入口节点数量是a，链表环内有b个节点，当快慢指针相遇时快慢指针分别走了f、s。此时可以得出 \(f=2s\)以及 \(f=nb+s\)，快指针比慢指针多走了n倍的环内节点数。两式相减得出\(s=nb\)。即第一次相遇时慢指针走了nb步。
- 一个指针k从头结点出发，经过\(k=a+nb\)步，一定能走到环的入口处。n取1、2、3、4。
- 由2、3步可知，如果想让慢指针走到环入口处，只需要再走a步就可以了。
- 保持慢指针位置不变，快指针移动到链表头结点，此时共同移动快慢指针，每次走一步，当再次相遇时，快慢指针一起走了a步，即慢指针走到了环的入口处。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for {
if fast == nil || fast.Next == nil {
return nil
}
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
break
}
}
fast = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return slow
}
今日收获
链表环的问题使用快慢指针来判断，由环的链表经过k=a+nb步，一定是环的入口位置（a是链表头结点到环的入口距离，b是环内节点数，n是环内圈数）。
通过推导得出慢指针走了nb步，只需要再走a步即可达到环的入口。