剑指15-反转链表

Posted on | In |

题目描述

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

链表的准备，构建四个节点的单链表，表头是phead：

1
2
3
4
5
6
7
8
9
10
11
12
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

nodeList = [Node(1),Node(2),Node(3),Node(4)]
phead = nodeList[0]
for i in range(len(nodeList)-1):
    nodeList[i].next = nodeList[i+1]
p = phead
while p is not None:
    p = p.next

辅助列表

遍历链表，用一个列表存储遍历到的所有节点，然后从后往前新建反转版本的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            return pHead
            
        mylist = []
        while pHead is not None:
            mylist.append(pHead)
            pHead = pHead.next
        for i in range(len(mylist)):
            if i == 0:
                mylist[i].next = None
            else:
                mylist[i].next = mylist[i-1]
        return mylist[-1]

递归的方法翻转链表

记输入链表是L0=phead+L1。既然用递归，则函数的输入是L0的表头phead，输出是新链表的表头，即L0的尾节点。内部调用自身的语句的输入应该是L1，其输出是L1的尾结点，也是L0的尾结点，新的表尾也就是L0的表头指向None。可知新链表的表头从递归的最深层，一路传送到最上层。亦可知，之后需要处理链表与子链表的衔接，即phead.next.next = phead; phead.next = None，L1的原表头即phead.next要指向phead。：

1
2
3
4
5
6
7
8
def reverseL(phead):
    if phead is None or phead.next is None:
        return phead
    
    node = reverseL(phead.next)
    phead.next.next = phead
    phead.next = None
    return node

非递归的方法翻转链表

  • 递归和非递归两种翻转方法，对输入的检测都是一样的逻辑if not phead or not phead.next: return phead
  • 每次循环，都要拿到前两个节点的指针p和q，循环以q.next的存在性判断是否终止
  • 更新p,q和连接时需要一个临时节点指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def reverseL(phead):
    if not phead or not phead.next:
        return phead
    p, q = phead, phead.next # 每次循环，要有前两个节点的指针
    while True:
        if q.next:
            temp = q # 临时变量
            q = q.next
            temp.next = p #
            p = temp
        else:
            q.next = p
            break
    phead.next = None
    return q