剑指Offer-反转链表

发表于 | 分类于

题目描述

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

解题思路

哎，惭愧，这题我没有做出来。然而，本应该是一道很基础的题目。我现在会两种写法，一是利用栈，二是利用头插法。这里就各自重写一次。另外，链表题要特别注意为空的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/

// 利用栈
class Solution {
public:
    ListNode* ReverseList1(ListNode* pHead) {
        if(pHead==NULL || pHead->next==NULL) return pHead;
        ListNode* p = pHead;
        stack<ListNode*> s;
        while(p->next){
            s.push(p);
            p = p->next;
        }
        ListNode* NewHead = p;
        while(!s.empty()){
            p->next = s.top();
            s.pop();
            p = p->next;
        }
        p->next = NULL;
        return NewHead;
    }

    ListNode* ReverseList2(ListNode* pHead) {
        if(pHead==NULL || pHead->next==NULL) return pHead;
        ListNode* p = pHead;
        ListNode* q = pHead->next;
        pHead->next = NULL;
        ListNode* r = NULL;
        while(q){
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        return p;
    }
}

最后还看到一种递归的写法，但是不太懂，就不写了。链表题通常要注意以下两点：

  1. 如果输入的头结点是 NULL，或者整个链表只有一个结点的时候
  2. 链表断裂的考虑