反转一个单链表。
示例:
输入: 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:
stack = []
res_Head = ListNode(0)
cur = res_Head
cnt = 0
while(head):
cnt += 1
stack.append(head.val)
head = head.next
while(cnt):
cur.next = ListNode(stack.pop())
cur = cur.next
cnt -= 1
return res_Head.next
递归实现:
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if(head == None or head.next == None):
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p