力扣206. 反转链表

Problem: 206. 反转链表

题目描述

思路

迭代写法：

1.定义前驱节点pre初始指向null，指针cur指向head；
2.遍历链表（退出条件是cur为空）:

2.1.定义一个nextP指针指向当前节点的下一个节点；
2.2.让cur的next指针指向pre指针；
2.3.使pre指向cur指针；
2.4.使cur指针指向nextP指针，并最后返回pre指针

递归写法:

(具体实现看代码实际操作！！！)由于我么需要翻转单链表，所以我们用递归去实现则需要在归的过程中去实现翻转操作

复杂度

时间复杂度:

$O(n)$;其中$n$为链表的长度

空间复杂度:

$O(n)$

Code

/**
 class Solution {
public:
    /**
     * Iteration
     *
     * @param head The head node of linked list
     * @return ListNode*
     */
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nextP = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nextP;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    /**
     * Recursion
     *
     * @param head The head node of linked list
     * @return ListNode*
     */
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head -> next == nullptr) {
            return head;
        }
        ListNode* res = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = nullptr;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18