141. 环形链表 Linked List Cycle

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：false

解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

代码1： 快慢指针

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func hasCycle(head *ListNode) bool {
  if head == nil || head.Next == nil {
    return false
  }
  slow, fast := head, head.Next
  for slow != fast {
    if fast == nil || fast.Next == nil {
      return false
    }
    slow, fast = slow.Next, fast.Next.Next
  }
  return true
}
func createRingNodeList(nums []int, pos int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  if pos >= 0 {
    p := head
    for pos > 0 {
      p = p.Next
      pos--
    }
    tail.Next = p
  }
  return head
}
func main() {
  nums, pos := []int{3, 2, 0, -4}, 1
  head := createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
  nums, pos = []int{1, 2}, 0
  head = createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
  nums, pos = []int{1}, -1
  head = createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
}

代码2： 哈希表

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func hasCycle(head *ListNode) bool {
  visited := make(map[*ListNode]bool)
  for head != nil {
    if visited[head] {
      return true
    }
    visited[head] = true
    head = head.Next
  }
  return false
}
func createRingNodeList(nums []int, pos int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  if pos >= 0 {
    p := head
    for pos > 0 {
      p = p.Next
      pos--
    }
    tail.Next = p
  }
  return head
}
func main() {
  nums, pos := []int{3, 2, 0, -4}, 1
  head := createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
  nums, pos = []int{1, 2}, 0
  head = createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
  nums, pos = []int{1}, -1
  head = createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
}

代码3： 递归

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func hasCycle(head *ListNode) bool {
  visited := make(map[*ListNode]bool)
  return checkCycle(head, visited)
}
func checkCycle(head *ListNode, visited map[*ListNode]bool) bool {
  if head == nil {
    return false
  }
  if visited[head] {
    return true
  }
  visited[head] = true
  return checkCycle(head.Next, visited)
}
func createRingNodeList(nums []int, pos int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  if pos >= 0 {
    p := head
    for pos > 0 {
      p = p.Next
      pos--
    }
    tail.Next = p
  }
  return head
}
func main() {
  nums, pos := []int{3, 2, 0, -4}, 1
  head := createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
  nums, pos = []int{1, 2}, 0
  head = createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
  nums, pos = []int{1}, -1
  head = createRingNodeList(nums, pos)
  fmt.Println(hasCycle(head))
}

输出：

true

false

142. 环形链表 II Linked List Cycle II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：返回索引为 0 的链表节点

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：返回 null

解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10^4] 内

-10^5 <= Node.val <= 10^5

pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

代码1：快慢指针

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return nil
  }
  slow, fast := head, head
  for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
    if slow == fast {
      slow = head
      for slow != fast {
        slow = slow.Next
        fast = fast.Next
      }
      return slow
    }
  }
  return nil
}
func createRingNodeList(nums []int, pos int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  if pos >= 0 {
    p := head
    for pos > 0 {
      p = p.Next
      pos--
    }
    tail.Next = p
  }
  return head
}
func showResult(head *ListNode) {
  if detectCycle(head) == nil {
    fmt.Println("null")
  } else {
    fmt.Println(detectCycle(head).Val)
  }
}
func main() {
  nums, pos := []int{3, 2, 0, -4}, 1
  head := createRingNodeList(nums, pos)
  showResult(detectCycle(head))
  nums, pos = []int{1, 2}, 0
  head = createRingNodeList(nums, pos)
  showResult(detectCycle(head))
  nums, pos = []int{1}, -1
  head = createRingNodeList(nums, pos)
  showResult(detectCycle(head))
}

代码2： 哈希表

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
  visited := make(map[*ListNode]bool)
  for head != nil {
    if visited[head] {
      return head
    }
    visited[head] = true
    head = head.Next
  }
  return nil
}
func createRingNodeList(nums []int, pos int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  if pos >= 0 {
    p := head
    for pos > 0 {
      p = p.Next
      pos--
    }
    tail.Next = p
  }
  return head
}
func showResult(head *ListNode) {
  if detectCycle(head) == nil {
    fmt.Println("null")
  } else {
    fmt.Println(detectCycle(head).Val)
  }
}
func main() {
  nums, pos := []int{3, 2, 0, -4}, 1
  head := createRingNodeList(nums, pos)
  showResult(detectCycle(head))
  nums, pos = []int{1, 2}, 0
  head = createRingNodeList(nums, pos)
  showResult(detectCycle(head))
  nums, pos = []int{1}, -1
  head = createRingNodeList(nums, pos)
  showResult(detectCycle(head))
}

代码3： 数组

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
  visited := make([]*ListNode, 0)
  for head != nil {
    for _, node := range visited {
      if node == head {
        return node
      }
    }
    visited = append(visited, head)
    head = head.Next
  }
  return nil
}
func createRingNodeList(nums []int, pos int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  if pos >= 0 {
    p := head
    for pos > 0 {
      p = p.Next
      pos--
    }
    tail.Next = p
  }
  return head
}
func showResult(head *ListNode) {
  if detectCycle(head) == nil {
    fmt.Println("null")
  } else {
    fmt.Println(detectCycle(head).Val)
  }
}
func main() {
  nums, pos := []int{3, 2, 0, -4}, 1
  head := createRingNodeList(nums, pos)
  showResult(detectCycle(head))
  nums, pos = []int{1, 2}, 0
  head = createRingNodeList(nums, pos)
  showResult(detectCycle(head))
  nums, pos = []int{1}, -1
  head = createRingNodeList(nums, pos)
  showResult(detectCycle(head))
}

输出：

null

143. 重排链表 Reorder List

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]

输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]

输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 10^4]

1 <= node.val <= 1000

代码：快慢指针 + 反转链表

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func reorderList(head *ListNode) {
  if head == nil || head.Next == nil {
    return
  }
  // 快慢指针找到中间节点
  slow, fast := head, head
  for fast.Next != nil && fast.Next.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
  }
  // 反转后半部分链表
  mid := slow.Next
  slow.Next = nil
  var prev *ListNode
  for mid != nil {
    next := mid.Next
    mid.Next = prev
    prev = mid
    mid = next
  }
  // 合并两个链表
  p1, p2 := head, prev
  for p2 != nil {
    next1 := p1.Next
    next2 := p2.Next
    p1.Next = p2
    p2.Next = next1
    p1 = next1
    p2 = next2
  }
}
func createNodeList(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  tail := head
  for i := 1; i < len(nums); i++ {
    tail.Next = &ListNode{Val: nums[i]}
    tail = tail.Next
  }
  return head
}
func (head *ListNode) travel() {
  for p := head; p != nil; p = p.Next {
    fmt.Print(p.Val)
    if p.Next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func main() {
  nums := []int{1, 2, 3, 4}
  head := createNodeList(nums)
  head.travel()
  reorderList(head)
  head.travel()
  nums = []int{1, 2, 3, 4, 5}
  head = createNodeList(nums)
  head.travel()
  reorderList(head)
  head.travel()
}

输出：

1->2->3->4<nil>

1->4->2->3<nil>

1->2->3->4->5<nil>

1->5->2->4->3<nil>

Golang每日一练(leetDay0048) 链表专题

141. 环形链表 Linked List Cycle

142. 环形链表 II Linked List Cycle II

143. 重排链表 Reorder List

热门文章

最新文章

相关电子书

推荐镜像

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

Golang每日一练(leetDay0048) 链表专题

141. 环形链表 Linked List Cycle

142. 环形链表 II Linked List Cycle II

143. 重排链表 Reorder List

热门文章

最新文章

相关电子书

推荐镜像