反转链表
算法知识视频讲解
时间限制：1秒 空间限制：64M
知识点
链表
iOS工程师
小米
2021
题目
题解(160)
讨论(2k)
排行
描述
输入一个链表，反转链表后，输出新链表的表头。
示例1
输入：
{1,2,3}
复制
返回值：
{3,2,1}
复制
关联企业
关联职位
相似企业真题

思路和心得：

1.遍历，原地改前后关系
需要pre
需要一个nxt_pos记录p结点下一个要解决的位置

python3

# -*- 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
        pre = None
        p = pHead
        nxt_pos = None
        while p:
            nxt_pos = p.next
            p.next = pre
            pre = p
            p = nxt_pos
        return pre

c++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution 
{
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
        ListNode * pre = NULL;
        ListNode * p = pHead;
        ListNode * nxt_pos = NULL;
        while(p)
        {
            nxt_pos = p->next;
            p->next = pre;
            pre = p;
            p = nxt_pos;
        }

        return pre;
    }
};