剑指Offer（十五）：反转链表

2017年12月7日10:11:41 8 11,045 °C
摘要

输入一个链表，反转链表后，输出链表的所有元素。

剑指Offer（十五）：反转链表

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入一个链表，反转链表后，输出链表的所有元素。

1、思路

这个很简单，我们使用三个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点。

在遍历的时候，做当前结点的尾结点和前一个结点的替换。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pReversedHead = NULL;
        ListNode* pNode = pHead;
        ListNode* pPrev = NULL;
        while(pNode != NULL){
            ListNode* pNext = pNode->next;
            if(pNext == NULL){
                pReversedHead = pNode;
            }
            pNode->next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        return pReversedHead;
    }
};

Python2.7：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- 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 or not pHead.next:
            return pHead
        last = None
        while pHead:
            tmp = pHead.next
            pHead.next = last
            last = pHead
            pHead = tmp
        return last

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：8   其中：访客  4   博主  4

    • avatar liying 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 电信 1
      回复 2018年8月15日 上午10:57  沙发

      你写的代码自己运行过吗？是错的

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
          回复 2018年8月15日 下午12:39  1层

          @liying 你运行了吗？就说是错的？都是牛客网ac后才复制过来的。

            • avatar liying 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 联通 1
              回复 2018年8月15日 下午1:42  2层

              @Jack Cui 试试链表第k个节点的next指针为第k-2的情况，牛客网并不是绝对的，还有我既然说了，当然是运行过了

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
                  回复 2018年8月15日 下午2:41  3层

                  @liying 你在说什么？你这是什么链表？Leetcode、牛客都是错的呗？

            • avatar 1 来自天朝的朋友 谷歌浏览器 Windows 10 山东省青岛市 电信 0
              回复 2019年9月16日 下午7:35  板凳

              为什么pNode = pNext;把pNext换成pNode->next就会出错呢？

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                  回复 2019年9月17日 上午9:22  1层

                  @1 pNode->next在前面已经更新了，应该用pNext临时变量保存的地址。

                • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市双城区 联通 2
                  回复 2020年7月20日 上午11:31  地板

                  看了一会，懂了思路：将原链表的前后结点的指向，都反向过来了，自然达到了反链表目的。学到了。