反转链表---C++实现_反转链表c++实现

/*
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：0<=n<=1000
要求：空间复杂度 O(1)，时间复杂度 O(n)。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
*/

/*
 * 假如有一个链表为：1 -> 2 -> 3 -> 4 -> 5 -> NULL
 *
 * 反转方案：<1>循环 <2>递归
 *
 * (循环)反转思路：
 *
 *            pHead
 *             |
 *         <1> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
 *
 *             pre   pHead  nex
 *              |      |    |
 *         <2> NULL <- 1 -> 2 -> 3 -> 4 -> 5 -> NULL       ---循环开始
 *
 *                     pre pHead  nex
 *                     |    |     /
 *         <3> NULL <- 1 <- 2 -> 3 -> 4 -> 5-> NULL
 *
 *                         pre  pHead  nex
 *                          |    |     /
 *         <4> NULL <- 1 <- 2 <- 3 -> 4 -> 5-> NULL
 *
 *                              pre  pHead  nex
 *                               |    |     /
 *         <5> NULL <- 1 <- 2 <- 3 <- 4 -> 5 -> NULL
 *
 *                                   pre  pHead  nex
 *                                    |    |      |
 *         <6> NULL <- 1 -> 2 -> 3 <- 4 <- 5 -> NULL
 *
 *                                        pre   pHead  nex
 *                                         |     |      |
 *         <7> NULL <- 1 -> 2 -> 3 -> 4 <- 5 -> NULL        ---循环结束
 *
 *                                        pre
 *                                         |
 *         <8> NULL <- 1 <- 2 <- 3 <- 4 <- 5
 */

//<1>循环
class Solution1 {
public:
    LNode *ReverseList(LNode *pHead) {
        if (pHead == NULL) {
            return NULL;
        }
        LNode *pre = NULL;
        LNode *nex = NULL;
        while (pHead) {
            //记录当前结点的下一结点
            nex = pHead->next;
            //改变当前结点的指向
            pHead->next = pre;
            //更新结点的位置
            pre = pHead;
            pHead = nex;
        }
        //当pHead为NULL时跳出循环，此时pre为新的头结点
        return pre;
    }
};

//<2>递归
class Solution2 {
public:
    LNode *ReverseList(LNode *pHead) {
        if (pHead == NULL) {
            return NULL;
        }
        LNode *pre = NULL;
        LNode *nex = NULL;
        //设置递归结束条件
        if (pHead->next == NULL) {
            pHead->next = pre;
            return pHead;
        }
        nex = pHead->next;
        pHead->next = pre;
        return ReverseList(nex);
    }
};
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92