题目¶
原题地址：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?
解法¶
遍历链表，通过修改节点的 next 属性翻转链表¶
通过修改当前节点的 next 属性指向前一个节点即可实现链表翻转。
这个方法的 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:
return head
pre = None
current = head
_next = None
while current is not None:
_next = current.next
current.next = pre
pre = current
current = _next
return pre
递归方法¶
递归的方法思路是：
- 把链表分为首节点（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