链表相关算法题

从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

题目解读：题目的大致意思链表是单向的，例如链表数值是 1，2，3，4，5，6
解题思路：我们需要可以反向输出为6，5，4，3，2，1 很明显我们通过链表是无法反向输出因为他是单向的，所有考虑例如栈的结构，存储数值，然后利用栈的特性，先进先出，也就是逐个遍历链表，一一入栈，然后在将一一出栈，每次都去获取栈顶，将其放入vector中下面是具体的代码实现

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
       stack <int> s;

       while (head != NULL) {
           s.push(head->val);
           head = head->next;
       }

       vector <int> vec;
       while (!s.empty()) {
           vec.push_back(s.top());
           s.pop();
       }

       return vec;
    }
};

链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

题目解读：由于链表是单向的，所以你无法知道距离末尾节点，倒数的节点，这时候需要通过一个辅助节点来帮你，节点1先向后移动指向到正着数第k个节点，然后跟着节点2指向头节点，节点1和节点2一起像后移动，则当节点指向尾节点时，节点2指向的是倒数第k个节点

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* p = head;
        ListNode* p1 = head;
        
        int j = 0;

        while (p != NULL) {
            if (j < k) {
                j++;
            } else {
                p1 = p1->next;
            }

            p = p->next;
        }

        return p1;
    }
};

反转链表
示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路：反转链表需要需要节点cur记录当前节点，一个节点pre记录上一个节点，所以当cur->next = pre 这时候就实现了反转了，当这时候也需要一个临时变量使cur节点可以向后移动，则先用temp = cur->next, 可以看看具体的代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head;
        ListNode *pre = NULL;
        ListNode *temp = NULL;

        while (cur != NULL) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp; 
        }

        return pre;
    }
}

最后这里return pre是以为当前节点cur = temp 跳出循环这时候 cur 指向了null，也就是尾节点多向后移动了一位，pre 是 cur的上一个节点才是真正的最后一位所以return pre；

最后编辑于：2020.06.19 21:11:03