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