Leetcode--Reverse Linked List

2018-06-27 10:06:04来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

转自请注明:http://www.cnblogs.com/igoslly/p/8670038.html  

 

      链表逆序在链表题目中还是较为常见的,这里将Leetcode中的两道题放在一起,分别是

0092 Reverse Linked List  II 0206 Reverse Linked List,0092在0206的基础上,提出了部分逆序的概念


 

首先来看0206,题目描述为:Reverse a singly linked list.

                也就是给出一个链表,要求我们将链表全部倒置链接

 

想法1: 定义一个堆栈,遍历链表时均push入堆栈,pop的顺序即为逆序

/**
 * 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) {
        stack<ListNode*> list_stack;  // 元素堆栈
        ListNode *p = head;
        
        // 当链表为空时,直接返回空
        if(head==NULL){return NULL;} 
        
        // 循环结束后,p为链表最后一个有值的结点(非NULL)
        while(p->next!=NULL){
            list_stack.push(p);
            p=p->next;
        }
        
        // 逆序表表头为原链表末结点,即为p
        head=p;
        while(!list_stack.empty()){
            ListNode *q = list_stack.top();
            list_stack.pop();
            p->next=q;
            p=p->next;
        }
        
        // 此时p是原链表首元素,新链表末元素,必须赋值NULL,否则提交回超时
        p->next=NULL;
        return head;
    }
};

按照此方法提交后,Leetcode runtime 是 9ms

程序的时间复杂度是 O(2n),因为遍历两次;

空间复杂度是 O(n),stack大小取决于原链表的大小。

 


 

想法2: 在遍历原链表时,直接创造新逆序链表,想法大概如下:

/**
 * 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 * new_head=NULL;
        while(head!=NULL){
            ListNode * next=head->next;
            head->next=new_head;
            new_head=head;
            head=next;
        }
        return new_head;
    }
};

这种方法程序的时间复杂度,因为只遍历了一遍,是 O(n),同时也没有耗费多余的空间


 

再看题目0092,题目描述是

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

要求原链表里[m,n]位置的结点进行逆序

同时保证输入m,n合法

 

注意: 这里结点计算从1开始

相对与题1来说,题2中相对于逆序段的逆序过程不变,只是多出了逆序段前后结点连接的问题,涉及到的结点有:

①逆序段开始的前一个结点   before_modify     ②逆序段开始的第一个结点 first_modify

逆序段结束的最后一个结点 last_modify        逆序段结束后的后一个结点 after_modify

正常的链表顺序是 -> -> ->

逆序后链表顺序是 -> -> ->

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode * pre_head =NULL,*p=head; 
        // pre_head=before_reverse,  p=first_reverse
        ListNode * new_head=NULL;
        int cnt=0; //count linked list position
        
        // 使用p和pre_head确定逆序段开始结点和前结点的位置
        while(p!=NULL){
            cnt++;
            if(cnt==m){break;}
            pre_head=p;p=p->next;
        }
        // 循环结束后,pre_head即为前结点位置(1),p为逆序段开始位置(2)
        
        // 因为后面循环p位置会改变,所以此时做下记录
        // 在逆序后,此结点(2)就作为逆序段末结点,直接连接后续的结点
        ListNode * reverse_first=p;
        
        // 逆序段开始逆序
        while(cnt<=n){
            ListNode *Next=p->next;
            p->next=new_head;
            new_head=p;
            p=Next;
            cnt++;
        }
        // 循环结束后,此时p为逆序段结束的后一个结点(4),连接在reverse_first(2)后面
        reverse_first->next=p;
        
        // 注意:当m=1时,pre_head=NULL,直接返回逆序链表的new_head即可
        // 否则,将new_head连接在前面正常后,返回原链表的head
        if(pre_head!=NULL){
            pre_head->next=new_head;return head;
        }else{
            return new_head;
        }
    }
};

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:WA自动鸡

下一篇:贪心算法推导 水题~