LeetCode: 206. Reverse Linked List

题目

原题地址:https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解法

递归方法

递归的方法思路是:

  • 把链表分为首节点(head)和剩余节点组成的链表 (reset)
  • 翻转剩余节点组成的链表,得到新的首节点(reset_head)
  • 然后再把原来的首节点(head)移到到翻转后的剩余链表的尾部(此时剩余链表的尾部是 head.next)
  • 返回新的首节点 reset_head

这个方法的 Python 代码类似下面这样:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        if head is None or head.next is None:
            return head

        reset_head = self.reverseList(head.next)
        reset_tail = head.next
        head.next = None
        reset_tail.next = head

        return reset_head

Comments

comments powered by Disqus