【EASY】Reverse Linked List

发布于: 2018-12-08 20:42
阅读: 79
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

  • A linked list can be reversed either iteratively or recursively. Could you implement both?

分析过程

  • 输入:一个链表
  • 输出:一个反向链表
  • 思路:循环方法,拷贝链表时反向指针即可。递归方法,递归找到最后一个节点,递归返回时候翻转指向。

解决方法

方法1:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) {
            return nullptr;
        }
        ListNode *newPre = new ListNode(head->val);
        ListNode *newTmp = nullptr;
        
        ListNode *tmp = head->next;
        
        while (tmp) {
            newTmp = new ListNode(tmp->val);
            newTmp->next = newPre;
            
            newPre = newTmp;
            tmp = tmp->next;
        }
        
        return newPre;
    }
};

方法2:

class Solution {
public:
    
    ListNode *_reverseList(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        // 和返回值一起看,达到递归条件时候,newRoot就是原链表的最后一个
        // root会随着递归返回,从倒数第二个开始一个一个往前移
        ListNode *newRoot = _reverseList(head->next);
        // 翻转指向
        // 原:3 - 4 - 5
        // 现:3 - 4 - 3
        // 下一步:2 - 3 - 4 -> 2 - 3 - 2
        // 一直到:0 - 1 - 2 -> 0 - 1 - 0
        head->next->next = head;
        // 3 - 4 - 3,成环,把环打断变成 4 - 3 - null
        // 下一步:3 - 2 - 3 -> 3 - 2 - null
        head->next = nullptr;
        
        return newRoot;
    }
    
    
    ListNode *reverseList(ListNode *head) {
        if (!head) {
            return nullptr;
        }
        // 先拷贝一份
        ListNode *newRoot = new ListNode(head->val);
        ListNode *newTmp = newRoot;
        ListNode *tmp = head->next;
        
        while (tmp) {
            newTmp->next = new ListNode(tmp->val);
            newTmp = newTmp->next;
            tmp = tmp->next;
        }
        // 反向
        return _reverseList(newRoot);
    }
};

Thanks for reading.

All the best wishes for you! 💕