206反转链表.md

题目描述

https://leetcode-cn.com/problems/reverse-linked-list/
反转一个单链表。

示例

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

---

思路一

先用栈储存链表，再出栈反转链表
显然，这样做时间、空间复杂度都不小

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> s;
        
        while( head != NULL ){
            s.push(head->val);
            head = head->next;
        }
        
        ListNode sentry(-1);
        ListNode *last = &sentry;
        while( s.size() != 0 ){
            ListNode *node = new ListNode(s.top());
            last->next = node;
            last = node;
            s.pop();
        }
        
        return sentry.next;
    }
};

---

思路二

一边读链表，一边反转

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if( head == NULL ) return NULL;
        if( head->next == NULL ) return head;
        
        // 第一个结点特殊处理
        ListNode *last = head;      // 上一个结点
        ListNode *p = head;         // 当前结点
        ListNode *temp = p->next;   // 暂存原结点的下一个结点
        p->next = NULL;
        p = temp;

        while( p != NULL ){
            temp = p->next;
            
            p->next = last;
            last = p;
            p = temp;
        }
        
        return last;
    }
};