35. Reverse linked list

题目

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

思考题：

请同时实现迭代版本和递归版本.
数据范围
链表长度 [0,30].

样例
输入:1->2->3->4->5->NULL

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

Iterative version code 1

Traverse from the first node and the second node to the next node of the tail node,Initially, the predecessor pointer points to the first node of the linked list

/** * 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* a = head, *b = head->next;//a为第一个节点,b为第二个节点
        while(b){
    //等价于a->next
            auto c = b->next;//临时保存b的下一个节点
            b->next = a;//b的next指针指向a
            a = b, b = c;//a和b往后移动一个节点
        }
        head->next = NULL;//For the reversed tail nodenext指针置为NULL;
        return a;//aThis is the inverted head node
    }
};

Iterative version code 2

Traverse from the head node to the tail node,Initially, the predecessor pointer points to 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) {
    
        ListNode * pre = nullptr;
        ListNode * cur = head;
        while(cur){
    //当curTraverse to the end of the linked list
            auto next = cur->next;//临时保存cur的下一个节点地址
            cur->next = pre;//Update the pointer of the current node
            pre = cur;//The predecessor node is moved to the current node
            cur = next;//当前节点移动到cur的下一个节点
        }
        return pre;//Returns the predecessor node of the original linked list tail node,That is, the head node after reversing the linked list
    }
};

递归版代码

• The key is to take advantage of the recursion end condition,Controlling the deepest recursion is at the tail nodereturn尾节点地址
• Because the recursive parameter is head->next,so immediately5->next==null满足递归结束条件head->next == nullWhen exiting to the previous level of recursion,,head为尾节点5的前驱节点4
• Execute two more lines of critical code to modify the node pointer
  • head->next->next = head;The purpose is through accesshead节点4,修改节点4的后继节点5的next指针指向节点4
  • head->next = null;目的是让当前head节点4指向空
• Because the return value of the previous recursive function call is always the one when the deepest recursion exitshead->next==null,That is, the tail node of the original linked list,一直没有发生变化

/** * 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;//如果链表为空,Or satisfy the recursion end conditionhead->next==null
        auto res = reverseList(head->next);//Save the head node returned to the final linked list,The return value is always the head node of the final linked list
        head->next->next = head;//When the deepest level recursively exits,即5->next == null时退出,The recursion end condition returns directlyhead,即res = head==5
                                //At this point, it returns to the recursion of the previous levelhead为4,The purpose of this line of code is to make 5的next指针指向4
        head->next = nullptr;//Let the current node point to null
        return res;//Returns the head node of the final linked list that has been saved,即head==5
    }
};