206 翻转链表
代码:
func reverseList(head *ListNode) *ListNode {
var dummy *ListNode
for head != nil{
temp := head.Next
head.Next = dummy
dummy = head
head = temp
}
return dummy
}
思路:
- 后一个节点指向前一个节点,需要用到的东西
- 前一个节点的指针
- 记录当前指针,以备下一个节点使用和位移一步
- 全部反转,第一个节点需要指向nil节点,开始时需要构造一个空节点
876.链表的中间节点
代码:
func middleNode(head *ListNode) *ListNode {
fast,slow := head,head
for fast != nil && fast.Next != nil{
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
思路:
- 快慢指针为链表第一解决思路
- 中间节点,意味两倍的关系
160.相交链表
代码:
func getIntersectionNode(headA, headB *ListNode) *ListNode {
i := headA
j := headB
for i != j {
if i == nil{
i = headB
}else{
i = i.Next
}
if j == nil{
j = headA
}else{
j = j.Next
}
}
return i
}
思路:
- A 和 B沿着到终点,遇到nil,到对方的跑道继续前进,最终会相遇;因为A走过的全部加B的路是相等的
141.环形链表
代码:
func hasCycle(head *ListNode) bool {
if head == nil{
return false
}
for i,j:=head,head.Next;j != nil && j.Next != nil;i,j = i.Next,j.Next.Next{
if i == j{
return true
}
}
return false
}
思路:
- 快慢指针,当两者相遇时,说明有环
- 循环条件为快指针是否为空,和快指针的Next是否为空。因为代码中快指针需要Next.Next
92.反转链表二
代码:
func reverse(head *ListNode)*ListNode{
var dummy *ListNode
for head != nil{
temp := head.Next
head.Next = dummy
dummy = head
head = temp
}
return dummy
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{
Next:head,
}
pre := dummy
// 反转前一个节点
for i:=0;i<left-1;i++{
pre = pre.Next
}
rightNode := pre
// 反转区间的最后一个节点
for j:=0;j<right-left+1;j++{
rightNode = rightNode.Next
}
// 记录另两个有用的节点
curr := rightNode.Next
leftNode := pre.Next
// 掐断连接,给反转函数干净的链表
rightNode.Next = nil
pre.Next = nil
// 反转部分链表
reverse(leftNode)
// 拼接反转部分
pre.Next = rightNode
leftNode.Next = curr
return dummy.Next
}
思路:
- 构造哑结点可以避免讨论
- 一共需记录四个节点,区间的首尾节点和区间外相邻的两个节点
- 将这部分依次反转
- 反转完开始拼接
328.奇偶链表
代码:
func oddEvenList(head *ListNode) *ListNode {
if head == nil{
return head
}
odd := head
even := head.Next
originEvenHead := head.Next
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
odd.Next = originEvenHead
return head
}
思路:
- 不用dummy node,因为偶链表需要拼接在奇链表后,需要以偶链表作为判空条件
- 最后偶链表判空,循环退出时,奇链表永远是非空的,所以可以直接赋值
- 不加哑结点,需要判断头结点是否为空