【EASY】Reverse Linked List

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

问题

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?

分析过程

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

解决方法

#include <iostream>
#include <map>

class Node {
public:
    int val;
    Node *next;
    
    Node(int val) {
        this->val = val;
        this->next = nullptr;
    }
    
    Node *copy() {
        return new Node(val);
    }
};

// 方法1,循环
Node *reserve1(Node *root) {
    Node *newPre = root->copy();
    Node *newTmp = nullptr;
    
    Node *tmp = root;
    
    while (tmp) {
        newTmp = tmp->copy();
        newTmp->next = newPre;
        
        newPre = newTmp;
        tmp = tmp->next;
    }
    
    return newPre;
}

// 方法2,递归
Node *_reserve2(Node *root);

Node *reserve2(Node *root) {
    // 先拷贝一份
    Node *newRoot = root->copy();
    Node *newTmp = newRoot;
    Node *tmp = root->next;
    
    while (tmp) {
        newTmp->next = tmp->copy();
        newTmp = newTmp->next;
        tmp = tmp->next;
    }
    // 反向
    return _reserve2(newRoot);
}

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

int main(int argc, const char * argv[]) {
    Node root = Node(0);
    Node n1 = Node(1);
    Node n2 = Node(2);
    Node n3 = Node(3);
    Node n4 = Node(4);
    Node n5 = Node(5);
    
    root.next = &n1;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    
    
    Node *newNode1 = reserve1(&root);
    Node *newNode2 = reserve2(&root);
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕