Note: A linked list can be reversed either iteratively or recursively. Could you implement both?
Example:
1. 迭代法
构建一个头结点,在遍历链表的过程中不断地采用头插法即可翻转链表。具体实现过程如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None
class : defreverseList(self, head: ListNode) -> ListNode: new_head = ListNode(0) p = head while p: tmp = p.next p.next = new_head.next new_head.next = p p = tmp return new_head.next
2. 递归法
递归的翻转后面的字符串,然后将当前的头结点放在最尾部,具体实现过程如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None
class : defreverseList(self, head: ListNode) -> ListNode: ifnot head ornot head.next: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_head
近期评论