单向链表反转

发表于 | 分类于 | 次

###题目

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

解题思路

下面一共2种方法：

最常见的是第1种，效率也高:

  1. 循环反转，逐个遍历；也相当于把链表的各个节点插入到头部

  2. 递归反转，逐个赋值，最后返回尾节点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # 三指针
        if pHead is None:
            return None
        if pHead.next is None:
            return pHead
        pre_node = None
        next_node = None
        while pHead is not None:
            next_node = pHead.next
            pHead.next = pre_node
            pre_node = pHead
            pHead = next_node
        return pre_node