10
2020
03

剑指offer题目训练4:从尾到头打印链表

输入一个链表的头结点,按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例

输入:[2, 3, 5]
返回:[5, 3, 2]
  1. 思路,本题思路比较多,如果要使用vector或者stack的话比较方便,这里奉上雪大的vector简单用法,主要用了

    vector.rbegin vector.rend 指针顺序是从尾到头输出的.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
         vector<int> res;
        //顺序遍历一遍存入vector
        while(head){
            res.push_back(head->val);
            head=head->next;
        }
        //rbegin,rend从尾到头new一个vector
        return vector<int>(res.rbegin(),res.rend());
        
    }
};
  1. 自己记得以前学c的时候学过链表反转,用的是双指针,没走一步把next反转过来直到最后一个元素,然后再遍历一遍新的链表即可。

    代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
         vector<int> res;
        if(head==NULL) return res;
        ListNode* p=head;
        ListNode* q=head->next;
        //p q双指针往后走
        while(q!=NULL){
            //r存储q下一步的位置
            ListNode* r=q->next;
            //到达最后一个元素,交换next,更改头指针
            if(q->next==NULL) {
              q->next=p;
              head->next=NULL;
              head=q;
              break;
            }
            //变换方向
            q->next=p;
            //继续往后走
            p=q;
            q=r;
         
        }
       
        //反转的链表进行遍历
        while(head!=NULL){
            res.push_back(head->val);
            head=head->next;
        }
        return res;
        
    }
};


« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。