qiaoxu123
11/21/2018 - 11:32 AM

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

test1.cpp
content_copyfile_download
//使用头插入的方式，建立一个新的链表
// 12 ms
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *temp = nullptr,*nextNode = nullptr;
        while(head){
            nextNode = head->next;
            head->next = temp;
            temp = head;
            head = nextNode;
        }
        return temp;
    }
};
test2.cpp
content_copyfile_download
//使用栈的方式进行逆序
//4 ms
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) 
            return head;
        stack<int> nodes;
        ListNode *p = head;
        ListNode *q = head;
        while(p){
            nodes.push(p->val);
            p = p->next;
        }
        while(!nodes.empty()){
            q->val = nodes.top();
            // cout << q->val << " ";
            q = q->next;
            nodes.pop();
        }
        return head;
    }
};