Leetcode链表(24,25,141,142,206)


Leetcode链表(24,25,141,142,206)

206 反转链表

  • 迭代
class Solution(object):
    def reverseList(self, head):
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev
  • 递归
class Solution(object):
	def reverseList(self, head):
		"""
		:type head: ListNode
		:rtype: ListNode
		"""
		if(head==None or head.next==None):
			return head
		cur = self.reverseList(head.next)
		head.next.next = head
		head.next = None
		return cur

24 两两交换链表中的节点

  • 递归
class Solution(object):
    def swapPairs(self, head):
        """
        if head == None or head.next == None:
            return head
        pre = head.next
        head.next = self.swapPairs(pre.next)
        pre.next = head
        return pre
  • 循环
class Solution(object):
    def swapPairs(self, head):
        pre = ListNode(-1)
        pre.next = head
        c = pre
        while c.next and c.next.next:
            a, b = c.next, c.next.next
            c.next, a.next = b, b.next
            b.next = a 
            c = c.next.next
        return pre.next

141 环形链表

  • set判重
class Solution(object):
    def hasCycle(self, head):
        cur = set()
        while head:
            if head in cur:
                return True
            else:
                cur.add(head)
                head = head.next
        return False
  • 双指针
class Solution(object):
    def hasCycle(self, head):
        last, fast = head, head
        while fast and last and fast.next:
            last = last.next
            fast = fast.next.next
            if last == fast:
                return True
        return False

142 环形链表II

  • set
class Solution(object):
    def detectCycle(self, head):
        cur = set()
        while head:
            if head in cur:
                return head
            else:
                cur.add(head)
                head = head.next
        return None
  • 快慢指针(floyd算法)
class Solution(object):
    def detectCycle(self, head):
        last, fast = head, head
        while fast and last and fast.next:
            last = last.next
            fast = fast.next.next
            if last == fast:
                cur = head
                pre = fast
                while cur != pre:
                    cur = cur.next
                    pre = pre.next
                return cur
        return None

25 K个一组反转链表

class Solution(object):
    def reverseKGroup(self, head, k):
        pre, end, pre.next, end.next = self, self, head, head

        while end:
            for i in range(k):
                if end is None:
                    break
                end = end.next
            if end is None:
                break
            start, _next, end.next = pre.next, end.next, None
            pre.next, start.next = self.reverse(start), _next
            end = pre = start
        return self.next

    def reverse(self, head):
        pre, curr = None, head
        while curr:
            curr.next, pre, curr = pre, curr, curr.next
        return pre

文章作者: Nczkevin
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Nczkevin !
评论
  目录