[LeetCode] 206. Reverse Linked List

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

2. 解题思路

  1. 注意:一般情况下,反转操作需要有两个指针
  2. 递归思路
    1. 递归类似于栈操作的入栈和出栈,关键在于入栈哪些数据?
    2. 针对这道题目,由于是反转操作,所以需要入栈两个指针,假定为prev和cur两个指针
    3. 为了能够反转,prev指针应该为cur的next指针,只有这样依次出栈的时候,prev指针才是指向反转链表过程中的prev节点
  3. 迭代思路
    1. 采用两个指针的头插法反转链表

3. 算法

3.1 递归算法
  1. 首先,需要确定递归函数的功能,此处的递归函数功能是返回原链表进行反转之后的头节点
  2. 递归结束条件:原链表为空或者原链表只有一个节点
3.2 迭代算法
  1. 创建一个哑节点用于向新链表的头部插入节点
  2. 用prev和cur两个指针进行反转操作

4. 实现

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
递归算法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        
        ListNode *new_prev = head->next; //存储新构成的链表的最后一个节点
        ListNode *new_head = reverseList(head->next); //反转从下一个节点开始的链表
        new_prev->next = head;
        head->next = NULL;
        return new_head;
    }
};
迭代算法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head;
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *head2 = &dummy;
        
        ListNode *prev = head2->next;
        ListNode *cur = prev->next;
        while(cur != NULL){
            prev->next = cur->next;
            cur->next = head2->next;
            head2->next = cur; //头插法
            cur = prev->next;
        }
        return dummy.next;
    }
};
posted @ 2020-02-14 20:25  wengle  阅读(...)  评论(...编辑  收藏

页面底部区域 foot.htm