0206.md

Reverse Linked List

题目

Reverse a singly linked list.

click to show more hints.

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

思路

遍历一次给定的链表，对于每一个值都生成一个cur的新结点，该新结点的next指向新生成的一个new_head(new_head 为 reverse list的第一个结点),然后 使new_head = cur循环到原链表的尾即可。

代码

迭代

/**
 * 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 *temp = head;
        ListNode *new_head = nullptr;
        
        while(temp){
            ListNode *cur = new ListNode(temp->val);
            cur->next = new_head;
            new_head = cur;
            temp = temp->next;
        }
        return new_head;
    }
};

递归

/**
 * 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 *temp = head;
        ListNode *new_head = nullptr;
        reverse(head,new_head);
        return new_head;
    }
    
    void reverse(ListNode* &head,ListNode* &new_head)
    {
        if(head){
            ListNode *cur = new ListNode(head->val);
            cur->next = new_head;
            new_head = cur;
            head = head->next;
            reverse(head,new_head);
        }
        
    }
};