5. 环形链表--判断是否有环
func hasCycle(head *ListNode) bool { first, second := head, head for first != nil && first.Next != nil { first = first.Next.Next second = second.Next if first == second { return true } } return false }
- 硬做
- Set
- 快慢指针
def hasCycle(self, head): fast = slow = head while slow and fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False
6. 环型链表 2
7. K 个一组翻转链表
优先队列
class Solution: # 翻转一个子链表，并且返回新的头与尾 def reverse(self, head: ListNode, tail: ListNode): prev = tail.next p = head while prev != tail: nex = p.next p.next = prev prev = p p = nex return tail, head def reverseKGroup(self, head: ListNode, k: int) -> ListNode: hair = ListNode(0) hair.next = head pre = hair while head: tail = pre # 查看剩余部分长度是否大于等于 k for i in range(k): tail = tail.next if not tail: return hair.next nex = tail.next head, tail = self.reverse(head, tail) # 把子链表重新接回原链表 pre.next = head tail.next = nex pre = tail head = tail.next return hair.next
func reverseKGroup(head *ListNode, k int) *ListNode { hair := &ListNode{Next: head} pre := hair for head != nil { tail := pre for i := 0; i < k; i++ { tail = tail.Next if tail == nil { return hair.Next } } nex := tail.Next head, tail = myReverse(head, tail) pre.Next = head tail.Next = nex pre = tail head = tail.Next } return hair.Next } func myReverse(head, tail *ListNode) (*ListNode, *ListNode) { prev := tail.Next p := head for prev != tail { nex := p.Next p.Next = prev prev = p p = nex } return tail, head }
