文档章节

offer--链表反转和从尾到头打印链表

r
 ranjiewen
发布于 2016/11/03 23:52
字数 875
阅读 6
收藏 0

       这个是高频的面试题,今天总结了一些。反转链表用三个指针实现,返回新链表的头节点;而从尾到头打印,应用栈实现,返回vector整个链表。

//题目描述
//
//输入一个链表,反转链表后,输出链表的所有元素。

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) :val(x), next(nullptr){}
};

//思路
//在反转链表的时候,我们很容易想到让当前结点的next指向前一个结点,
//但是这样做了之后这个节点原本next所指的结点就找不回了,所以每次我们都要保存新的前一结点,
//当前结点和下一结点三个指针,只要下一结点为空,那么我们就到了原本结点的尾部,这时正是新链表的头部
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {

        ListNode *current = pHead;
        ListNode *pre = nullptr;
        ListNode *pNewNode = nullptr;
        if (pHead == nullptr)
        {
            return nullptr;
        }
        while (current != nullptr)  //当前结点不为空
        {
            ListNode *pnext = current->next; //当前结点的后继
            if (pnext == nullptr)
            {
                pNewNode = current;  //最后结点,即反转链表的头节点
            }
            current->next = pre; //当前结点的后继转为前驱
            pre = current;  //前驱转为当前结点
            current = pnext;  //当前结点向后移
        }
        return pNewNode;
    }
};

//1、三个指针在链表上同时滑动,比较容易想到但是编码略复杂
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        if (pHead->next == nullptr) return pHead;

        ListNode *pBefore = pHead, *p = pHead->next, *pAfter = p->next;
        while (pAfter) {
            p->next = pBefore; // reverse
            pBefore = p;
            p = pAfter;
            pAfter = pAfter->next;
        }
        p->next = pBefore; //完成最后一个结点的前驱
        pHead->next = nullptr; //尾结点后继为空
        return p;
    }
};

//2、从原链表的头部一个一个取节点并插入到新链表的头部
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        ListNode* head = pHead;
        pHead = pHead->next;
        head->next = nullptr; //此时的head为尾结点
        while (pHead) {
            ListNode *next = pHead->next;
            pHead->next = head;
            head = pHead; //
            pHead = next;
        }
        return head;
    }
};

//使用一个栈来解决问题,C++

#include<stack>
using namespace std;
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr)
        {
            return pHead;
        }
        ListNode * p = pHead;
        ListNode * newHead;
        stack<ListNode *> stack1;
        while (p->next != NULL)
        {
            stack1.push(p);
            p = p->next;
        }
        newHead = p;
        while (!stack1.empty())
        {
            p->next = stack1.top();
            p = p->next;
            stack1.pop();
        }
        p->next = NULL;
        return newHead;
    }
};


//题目描述
//
//输入一个链表,从尾到头打印链表每个节点的值。
//输入描述 :
//输入为链表的表头
//
//
//输出描述 :
//输出为需要打印的“新链表”的表头
#include<vector>
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {

        //std::stack<ListNode*> nodes;

        // ListNode *pNode = head;
        // while(pNode != NULL)
        // {
        //      nodes.push(head);
        //      head = head->next;
        // }

        //  while(!nodes.empty())
        //  {
        //     head = nodes.top();
        //     printf("%d\t" ,head->val);
        //     nodes.pop();
        //  }

        vector<int> dev1;
        if (head != NULL)
        {
            if (head->next != NULL)
            {
                dev1 = printListFromTailToHead(head->next);
            }
            dev1.push_back(head->val);
        }
        return dev1;

    }
};

class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        //利用栈的逆序输出特性       
        stack<int> stack;
        vector<int> vector;
        struct ListNode *p = head;
        if (head != NULL) {
            stack.push(p->val);
            while ((p = p->next) != NULL) {
                stack.push(p->val);
            }
            while (!stack.empty()) {
                vector.push_back(stack.top());
                stack.pop();
            }
        }
        return vector;
    }

};

/***
*从原理上来说,借助栈会使得问题的解决思路非常简单明了。
*注意函数的返回类型是int类型的vector
*/
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head)
    {
        vector<int> vec;         //声明一个vector存放Node的int类型的val值
        std::stack<ListNode *>nodes;
        ListNode *pNode = head;
        //遍历入栈
        while (pNode != NULL)
        {
            nodes.push(pNode);    //遍历所有节点,将结点压入栈中
            pNode = pNode->next;
        }
        //遍历出栈
        while (!nodes.empty())
        {
            pNode = nodes.top();        //定义的结点指针始终指向栈顶,取出栈顶结点的val值存入到定义的vec中,然后弹出栈顶元素。由栈顶往栈底遍历
            vec.push_back(pNode->val);
            nodes.pop();
        }
        return vec;    //返回值为int型的vector
    }
};

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5515908.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
剑指Offer学习总结-从尾到头打印链表

剑指Offer学习总结-从尾到头打印链表 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000
2018/01/16
0
0
[剑指offer] 从尾到头打印链表

本文首发于我的个人博客:尾尾部落 题目描述 输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。 解题思路 一种方法是利用栈来实现; 另外一种方法是利用三个指针把链表反转,关键是 ...

繁著
2018/08/09
0
0
链表面试题(上)

一、题目 1、从尾到头打印单链表 (有四种方法) 2、删除一个无头单链表的非尾节点(不能遍历链表) 3、在无头单链表的一个节点前插入一个节点(不能遍历链表) 4、单链表实现约瑟夫环(Joseph...

qq_38646470
2018/01/04
0
0
经典链表练习题(1)

问题: 从尾到头打印单链表 删除一个无头单链表的非尾节点(不能遍历链表) 在无头单链表的一个节点前插入一个节点(不能遍历链表) 单链表实现约瑟夫环(JosephCircle) 逆置/反转单链表 单链...

triorwy
2018/01/23
0
0
左程云著算法与数据结构题目最优解笔记-链表

#链表 链表是面试时被提及最频繁的数据结构。链表就是通过指针将一个个节点连接起来。链表是非连续的动态内存空间,链表的查找比数组慢,但是添加和删除比数组快。 ###链表声明 public class...

hiyoung
2018/09/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
今天
533
10
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合(类似mysql 中的 表): 后面我们大部分都...

TcWong
今天
31
0
spring cloud

一、从面试题入手 1.1、什么事微服务 1.2、微服务之间如何独立通讯的 1.3、springCloud和Dubbo有哪些区别 1.通信机制:DUbbo基于RPC远程过程调用;微服务cloud基于http restFUL API 1.4、spr...

榴莲黑芝麻糊
今天
16
0
Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
47
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
56
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部