剑指offer-反转链表

你的名字 2022-02-14 09:19 248阅读 0赞

#### 题目描述 ####

输入一个链表，反转链表后，输出新链表的表头。

#### 实现思想 ####

有以下几种实现思想。  
我用的实现思想（第一种）：利用栈的原理，申请一个节点栈，将链表上的节点从头到尾一个一个压入栈，然后申请一个新的链表，将栈中的节点一个一个弹出到链表中，并将链表最后节点的next指向null就可以了。  
利用循环的思想（第二种）：申请三个指针，一个指向前一个，一个指向当前，一个指向后一个。让当前指针的next指向前一个，实现了反转，然后移动前一个指针指向当前指针，移动当前指针指向后一个指针，后一个指针也后移一个（其实就是三个指针都后移然后进行下一个节点的反转）。总的思想用一句话总结：将当前链表直接反向所有的next指针。

#### 算法实现 ####

第一种思想算法的实现：

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* ReverseList(ListNode* pHead) {
            if(pHead == NULL) return NULL;
            if(pHead->next == NULL) return pHead;
            stack<ListNode*> stack_listnode;
            while(pHead != NULL) {
                stack_listnode.push(pHead);
                pHead = pHead->next;
            }
            ListNode* q = stack_listnode.top();
            ListNode* qHead = q;
            stack_listnode.pop();
            while(stack_listnode.size() != 0) {
                q->next = stack_listnode.top();
                stack_listnode.pop();
                q = q->next;
            }
            q->next = NULL;
            return qHead;
        }
    };

第一种思想总的反转实现（带main函数）：

#include <stdc++.h>
    using namespace std;
    
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };
    class Solution {
    public:
        ListNode* ReverseList(ListNode* pHead) {
            if(pHead == NULL) return NULL;
            if(pHead->next == NULL) return pHead;
            stack<ListNode*> stack_listnode;
            while(pHead != NULL) {
                stack_listnode.push(pHead);
                pHead = pHead->next;
            }
            ListNode* q = stack_listnode.top();
            ListNode* qHead = q;
            stack_listnode.pop();
            while(stack_listnode.size() != 0) {
                q->next = stack_listnode.top();
                stack_listnode.pop();
                q = q->next;
            }
            q->next = NULL;
            return qHead;
        }
    };
    
    int main()
    {
        Solution S;
        ListNode* pHead = new ListNode(0);
        ListNode* Head = pHead;
        //将链表中输入数据0-9
        for(int i=1;i<10;i++) {
            ListNode* temp = new ListNode(i);
            pHead->next = temp;
            pHead = pHead->next;
        }
        pHead = Head;
        //执行反转操作
        ListNode* p = S.ReverseList(pHead);
        //打印反转后的链表数据
        for(;p != NULL;p = p->next) {
            cout<< p->val << endl;
        }
    
        cout << "hello world!" << endl;
        return 0;
    
    }

#### 运行截图 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]

#### 总结 ####

① 申请节点栈的方法是：`stack<ListNode*> stack_listnode;`不要忘了 \* ，因为整个ListNode \* 是一个类型。  
② 栈的pop操作没有返回值，所以使用的时候先用top操作返回栈顶元素，然后用pop操作弹出栈顶元素。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]: /images/20220214/8a138f575cdc41f98962b12879c03fd2.png