14
LeetCode: 206. Reverse Linked List
source link: https://mozillazg.com/2020/10/leetcode-206-reverse-linked-list.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目¶
原题地址：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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK