三个月算法进阶--day38

2020-09-30 约 358 字预计阅读 1 分钟次阅读

反转链表

复杂的递归

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        ptr1, ptr2 = head, head.next
        while ptr2.next:
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        ptr2.next = ptr1
        ptr1.next = None
        self.reverseList(head)
        return ptr2

反复的迭代

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        length = 1
        prev = head
        ptr = head.next
        while ptr2:
            length += 1
            ptr = ptr.next
            prev = prev.next
        for i in range(length-1, 0, -1):
            count = 1
            ptr1 = head
            ptr2 = head.next
            while count != i:
                count += 1
                ptr1 = ptr1.next
                ptr2 = ptr2.next
            ptr2.next = ptr1
            ptr1.next = None
        return prev

简单的递归

class Solution(object):
	def reverseList(self, head):
		"""
		:type head: ListNode
		:rtype: ListNode
		"""
		if not head or not head.next:
			return head
		cur = self.reverseList(head.next)
		head.next.next = head
		head.next = None
		return cur

递归调用过程

reverseList: head=1
    reverseList: head=2
	    reverseList: head=3
		    reverseList:head=4
			    reverseList:head=5 
				返回5
			cur = 5
			4.next.next->4, 4.next->null 即5->4->null
		cur=5
		3.next.next->3, 3.next->null 即5->4->3->null
	cur = 5
	2.next.next->2, 2.next->null 即5->4->3->2->null
cur = 5
1.next.next->1, 1.next->null 即5->4->3->2->1->null

一次迭代

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        prev = None
        ptr = head
        while ptr:
            temp = ptr.next
            ptr.next = prev
            prev = ptr
            ptr = temp
        return prev

目录

三个月算法进阶--day38

反转链表