Leetcode0092 & 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： 在遍历原链表时，直接创造新逆序链表，想法大概如下：

/**

 * 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 ≤ m ≤ n ≤ 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=; //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;

        }

    }

};

巴特西

Leetcode0092 & 0206--Reverse Linked List 链表逆转

最新文章

热门文章