《剑指offer刷题笔记》23、反转链表【c++详细题解】

偏执的太偏执、 2021-07-25 02:07 357阅读 0赞

### 题目 ###

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

**思考题：**

*  请同时实现迭代版本和递归版本。

**样例**

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

### **思路1** ###

**(链表操作，迭代)**  ( n ) (n) (n)  
翻转即将所有节点的next指针指向前驱节点。  
由于是单链表，我们在迭代时不能直接找到前驱节点，所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前，不要忘记保存它的后继节点。

空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是  O ( 1 ) O(1) O(1)  
时间复杂度分析：只遍历一次链表，时间复杂度是 O ( n ) O(n) O(n)。

### **代码1** ###

/** * 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) { 
            ListNode *pre = NULL;
            ListNode *cur = head;
            while(cur)
            { 
                ListNode *next = cur->next; //保留后继节点
                cur->next = pre; //当前节点指向前驱节点
                pre = cur, cur = next;
            }
            return pre;
        }
    };

### **思路2** ###

**(链表操作，递归)**  O ( n ) O(n) O(n)  
首先我们先考虑 `reverseList` 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。  
所以我们可以先递归处理`reverseList(head->next)`，这样我们可以将以`head->next`为头节点的链表翻转，并得到原链表的尾节点`tail`，此时`head->next`是新链表的尾节点，我们令它的`next`指针指向`head`，并将`head->next`指向空即可将整个链表翻转，且新链表的头节点是`tail`。

空间复杂度分析：总共递归 n n n 层，系统栈的空间复杂度是  O ( n ) O(n) O(n)，所以总共需要额外  O ( n ) O(n) O(n)的空间。  
时间复杂度分析：链表中每个节点只被遍历一次，所以时间复杂度是  O ( n ) O(n) O(n)。

### **代码2** ###

/** * 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 || !head->next) return head;
            ListNode *tail = reverseList(head->next);
            head->next->next = head;
            head->next = nullptr;
            return tail;
        }
    };