问题描述:
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
首先是迭代方式:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or head.next == None:
return head
p1=None
p2=head
while p2:
t=p2.next
p2.next = p1
p1 = p2
p2 = t
return p1
过程:
关键之处,先要找到p2的下一个节点,然后再断开p2.next并指向p1
然后p1,p2同时右移,保证p1每次都在p2的前面
这样每次就可以让p2.next=p1
结果:
递归版本的:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or head.next == None:
return head
p1=head.next
p2=self.reverseList(p1)
head.next=None
p1.next=head
return p2
过程:
首先是:
然后是以p1为头结点的链表:
依次类推直到头结点不为空或头结点的下一节点不为空,也就是:
此时此时返回的值就是p2,也就是最后一个节点。之后就翻转当前的链表:
依次递推即可:
需要明确的是:先会一直执行:
p2=self.reverseList(p1)
得到返回值之后才会执行:
head.next=None
p1.next=head
最后返回p2即可。
结果: