剑指offer-反转链表-链表-python

题目描述

输入一个链表，反转链表后，输出新链表的表头。

 

思路很简单：1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。需要考虑链表只有1个元素的情况。图中有具体的每步迭代的思路，最后输出pre而不是cur是因为最后一次迭代后cur已经指向None了，而pre是完整的反向链表。

链接：https://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca?f=discussion
来源：牛客网

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        pre = None
        cur = pHead
        while cur!=None:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

思路2：

将原来所有节点组成一个数组，翻转数组，再将数组中的每个加点连接起来。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead:
            return
        res = []
        while pHead:
            res.append(pHead)
            pHead = pHead.next
        res.reverse()
        for i in range(0,len(res)):
            cur = res[i]
            if i == len(res)-1:
                cur.next = None
            else:
                cur.next = res[i+1]
        return res[0]