我命由我,不由天!


  • 搜索
prometheus docker golang linux kubernetes

leetcode链表相关

发表于 2021-07-07 | 0 | 阅读次数 393

206 翻转链表

image20210706212128619.png
代码:

func reverseList(head *ListNode) *ListNode {
    var dummy *ListNode
    for head != nil{
        temp := head.Next
        head.Next = dummy
        dummy = head
        head = temp
    }
    return dummy
}

思路:

  1. 后一个节点指向前一个节点,需要用到的东西
    1. 前一个节点的指针
    2. 记录当前指针,以备下一个节点使用和位移一步
  2. 全部反转,第一个节点需要指向nil节点,开始时需要构造一个空节点

876.链表的中间节点

image20210706213935882.png
代码:

func middleNode(head *ListNode) *ListNode {
    fast,slow := head,head
    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

思路:

  1. 快慢指针为链表第一解决思路
  2. 中间节点,意味两倍的关系

160.相交链表

image20210706234050370.png
代码:

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
}

思路:

  1. A 和 B沿着到终点,遇到nil,到对方的跑道继续前进,最终会相遇;因为A走过的全部加B的路是相等的

141.环形链表

image20210706234650363.png
代码:

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
}

思路:

  1. 快慢指针,当两者相遇时,说明有环
  2. 循环条件为快指针是否为空,和快指针的Next是否为空。因为代码中快指针需要Next.Next

92.反转链表二

image20210707003933038.png
代码:

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

}

思路:

  1. 构造哑结点可以避免讨论
  2. 一共需记录四个节点,区间的首尾节点和区间外相邻的两个节点
  3. 将这部分依次反转
  4. 反转完开始拼接

328.奇偶链表

image.png

代码:

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
}

思路:

  1. 不用dummy node,因为偶链表需要拼接在奇链表后,需要以偶链表作为判空条件
  2. 最后偶链表判空,循环退出时,奇链表永远是非空的,所以可以直接赋值
  3. 不加哑结点,需要判断头结点是否为空
  • 本文作者: Dante
  • 本文链接: https://gaodongfei.com/archives/leetcode-链表复习
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
线性表
leetcode-栈相关习题
  • 文章目录
  • 站点概览
Dante

Dante

119 日志
5 分类
5 标签
RSS
Creative Commons
0%
© 2023 Dante
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4
沪ICP备2020033702号