欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Leetcode--Reverse Linked List

程序员文章站 2024-01-03 08:02:46
转自请注明:http://www.cnblogs.com/igoslly/p/8670038.html 链表逆序在链表题目中还是较为常见的,这里将Leetcode中的两道题放在一起,分别是 0092 Reverse Linked List II 和 0206 Reverse Linked List, ......

转自请注明: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: 在遍历原链表时,直接创造新逆序链表,想法大概如下:

Leetcode--Reverse Linked List

/**
 * 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;
        }
    }
};

 

上一篇:

下一篇: