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
-
31
LeetCode 是著名的练习数据结构与算法的网站，很多学习程序设计的人都在刷上面的题来巩固和提高自己的数据结构以及算法的能力。同时，该网站的很多数据结构及算法题都是面试中的真题。 我刷过的题目不算多，我准备把我做过的题目再逐步的整理一下。虽...
-
10
题目¶ 原题地址：https://leetcode.com/problems/design-linked-list/ De...
-
10
解法¶ 遍历链表，记录访问过的节点，找出环开始的节点...
-
17
Prerequisites To learn how to reverse singly linked lists, you should know: Python 3 Python data structures - List In place list reversal...
-
14
Leetcode 114. Flatten Binary Tree to Linked List 当前位置：XINDOO > 算法 > 正文 ...
-
9
LeetCode 第 206 号问题：反转链表-程序员小吴 当前位置：程序员小吴 > LeetCodeAnimation > LeetCode 第 206 号问题：反转链表 ...
-
9
How do you reverse a singly linked list? How to reverse a linked list is one of the most commonly asked data structures interview questions. Here we have both an iterative and a recursive solution for this problem. Let’s start wit...
-
6
Reverse a Linked List in groups of given sizeSkip to content
-
7
Reverse a Linked List in group of given sizeSeptember 02, 2023 |260 ViewsSDE Sheet - Reverse a Linked List in group of given sizeSDE Sheet, GFG SDE Sheet, linked-list Save Share ...
-
8
Reverse alternate nodes in Linked ListOctober 07, 2023 |1.1K ViewsPROBLEM OF THE DAY: 06/10/2023 | Reverse alternate nodes in Linked ListProblem of the Day, linked-list, Data Structure and Alg...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK