剑指offer——从尾到头打印链表节点的值


输入一个链表,从尾到头打印链表每个节点的值。

输入描述:输入为链表的表头

输出描述:输出为需要打印的“新链表”的表头


 

一、问题分析


 

  初拿到这个题目时,这应该是考察单向链表这一数据结构。单向链表的遍历总是从头指针逐项遍历各个节点,现在要求从尾到头打印节点的值,我们可以在遍历时把各节点压入栈内,最后出栈打印各个节点值,即可达到要求。

  实现之前,我们先来看看如何创建一个链表。

  1,链表节点的数据结构定义

1 struct ListNode {
2     int val;
3     struct ListNode *next;
4     ListNode(int x) :
5         val(x), next(NULL) {
6         }
7 };

  在链表的定义中,包含自己的整形成员(当然也可以定义为其它数据类型,如double),以及下一个节点的位置信息(next)。这里我们还定义了节点的构造函数(ListNode),方便节点的初始化。

  2,链表的创建

  这里我们考虑单向链表。如果通过用户输入来创建链表,我们可以进行如下操作:

  1)创建头节点head,指向NULL。因为此时没有任何节点

  2)为加入的节点分配空间,赋初值(如1中考虑的int类型)并指向NULL。判断head==NULL?head指向该节点:“上一节点”指向该节点

  3)更新新加入的节点为“上一节点”

  4)判断节点是否添加结束,若否,重复2,3,4步骤继续添加节点。


 

二、问题的解决思路


 

  1,利用stack反转输出链表节点值

剑指offer——从尾到头打印链表节点的值剑指offer——从尾到头打印链表节点的值

  1 #include <iostream>
  2 #include <vector>
  3 #include <stack>
  4 using namespace std;
  5 
  6 //链表节点定义
  7 struct ListNode {
  8     int val;
  9     struct ListNode *next;
 10     ListNode(int x) :
 11         val(x), next(NULL) {
 12         }
 13 };
 14 
 15 //链表从尾到头输出节点值方法实现
 16 class Solution {
 17     public:
 18         //方法1,通过stack 这个container来实现反转链表
 19         vector<int> printListFromTailToHead(struct ListNode* head) {
 20             vector<int> result;
 21             if(head == NULL)
 22                 return result;
 23             stack<ListNode*> reverse;
 24             ListNode* node = head;
 25             while(node != NULL) {
 26                 reverse.push(node);
 27                 node = node->next;
 28             }
 29             while(!reverse.empty()) {
 30                 node = reverse.top();
 31                 result.push_back(node->val);
 32                 reverse.pop();
 33             }
 34             return result;
 35         }
 36         //方法2,原地反转链表,不介入其它container
 37         //不断的使“下一个节点”指向“前一个”节点
 38         vector<int> printListFromTailToHead2(struct ListNode* head) { 
 39             vector<int> vec; 
 40             ListNode *buf = head; 
 41             ListNode *pre = buf; 
 42             if(head == NULL) 
 43                 return vec; 
 44             while(head->next != NULL){ 
 45                 buf = head->next; 
 46                 head->next = buf->next; 
 47                 buf->next = pre; 
 48                 pre = buf; 
 49             } 
 50             while(buf){ 
 51                 vec.push_back(buf->val); 
 52                 buf = buf->next; 
 53             } 
 54             return vec; 
 55         }
 56 };
 57 
 58 struct ListNode* CreateListNode(struct ListNode* head) {
 59     struct ListNode *p1, *p2;
 60     int i = 1;
 61     p1 = p2 = (struct ListNode*)malloc(sizeof(ListNode));
 62     cout << "Please input the 1st node, it's address is p1_addr = " << p1 << endl;
 63     cout << "And input -1 to quit.";
 64     cin >> (p1->val);
 65     p1->next = NULL;
 66 
 67     while (p1->val != -1) {
 68         if (NULL == head) {
 69             head = p1;
 70         }
 71         else
 72             p2->next = p1;
 73         p2 = p1;
 74         p1 = (struct ListNode*)malloc(sizeof(ListNode));
 75         ++i;
 76         cout << "Please input the " << i << " node," << "it's address is p" << i << "_addr = " << p1 <<endl;
 77         cin >> (p1->val);
 78     }
 79     free(p1);
 80     p2->next = NULL;
 81     p1 = NULL;
 82     cout << "End of creating ListNode." << endl;
 83     return head;
 84 }
 85 
 86 int main () {
 87     std::vector<int> v;
 88     struct ListNode* head = NULL;
 89     head = CreateListNode(head);
 90 
 91     Solution s;
 92     v = s.printListFromTailToHead2(head);
 93     for (int var : v) {
 94         cout << var << ' ';
 95     }
 96 
 97     //测试节点的初始化,与本题无关
 98     struct ListNode myListNode(100);
 99     cout << myListNode.val << endl;
100 
101 }

View Code

  上述程序在gcc version 6.1.0下编译通过。

  在上面的程序中,实现反转的方法有两个:

  1)利用stack先入后出的特性实现链表的反转

  2)不借用其它container,不断的使“后一个”节点指向“前一个节点”来原地反转链表。下面来谈谈原地反转链表

  2,原地反转链表

  我们看函数printListFromTailToHead2()。首先,我们先定义两个指针(buf, pre),并与head共同指向链表的头节点。然后,通过head->next遍历原始链表,并同时更新buf指向已经遍历到的节点(buf = head->next),而这期间head始终指向头节点。然后,更新head—>next指向buf的下一个节点(head->next = buf->next)。接着,通过buf->next = pre, 使buf指向前一个节点,紧接着更新pre,使其指向当前节点,以便下一轮更新。

  当head->next遍历完链表后,buf指向了原始链表最后一个节点,head->next的值变为了NULL。现在从buf开始遍历,即可反向遍历链表。