[LeetCode]92.Reverse Linked List II

简介:

【题目】

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->NULLm = 2 and n = 4,

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

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

【题意】

将给定链表第m个节点到第n个节点的位置逆序,返回逆序后的链表。
给定M,N满足以下条件: 
1≤M≤N≤列表的长度。

【分析】

思路1:

前m-1个不变,从第m+1个到第n个,依次删除,用尾插法插入到第m-1个节点后面。

    第一步把4节点删除放入2节点之后

 第二步把5节点删除放入2节点之后

【代码1】

/*********************************
*   日期:2014-01-28
*   作者:SJF0115
*   题号: Reverse Linked List II
*   来源:http://oj.leetcode.com/problems/reverse-linked-list-ii/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(m > n || n < 0){
            return head;
        }
        ListNode *tail,*p,*rTail,*pre = NULL;
        //添加虚拟头结点(便于反转全部)
        ListNode *beginNode = (ListNode*)malloc(sizeof(ListNode));
        beginNode->next = head;
        pre = beginNode;

        int index = 1;
        //遍历前m-1个节点
        while(pre != NULL && index < m){
            pre = pre->next;
            index++;
        }
        tail = pre;
        rTail = pre->next;
        index = 1;
        //删除第m+1节点开始
        while(index < (n-m+1) ){
            //删除p节点
            p = rTail->next;
            rTail->next = p->next;
            //尾插法
            p->next = tail->next;
            tail->next = p;
            index++;
        }
        return beginNode->next;
    }
};
int main() {
    Solution solution;
    int A[] = {1,2,3,4,5,6,7,8,9};
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *node;
    ListNode *pre = head;
    for(int i = 0;i < 1;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }
    head = solution.reverseBetween(head->next,1,8);
    while(head != NULL){
        printf("%d ",head->val);
        head = head->next;
    }
    return 0;
}


【代码2】

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(0);
        dummy.next = head;

        ListNode *preM, *pre = &dummy;
        for (int i = 1; i <= n; ++i) {
            //preM 第m-1个节点
            if (i == m) preM = pre;
            if (i > m && i <= n) {
                //删除head节点
                pre->next = head->next;
                head->next = preM->next;
                //尾插法
                preM->next = head;
                head = pre; // head has been moved, so pre becomes current
            }
            pre = head;
            head = head->next;
        }
        return dummy.next;
    }
};


目录
相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
59 1
|
C++
Leetcode Copy List with Random Pointer(面试题推荐)
给大家推荐一道leetcode上的面试题,这道题的具体讲解在《剑指offer》的P149页有思路讲解,如果你手头有这本书,建议翻阅。
59 0
Leetcode 19.Remove Nth Node From End of List
删除单链表中的倒数第n个节点,链表中删除节点很简单,但这道题你得先知道要删除哪个节点。在我的解法中,我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点,这样是为了把删除头节点的特殊情况转换为一般情况,代码如下。
48 0
|
9月前
|
大数据 Java 程序员
「LeetCode合集」链表(List)及经典问题
「LeetCode合集」链表(List)及经典问题
60 0
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode 237. 删除链表中的节点 Delete Node in a Linked List
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode Contest 178-1367. 二叉树中的列表 Linked List in Binary Tree
LeetCode 382. Linked List Random Node
给定一个单链表,随机选择链表的一个节点,并返回相应的节点值。保证每个节点被选的概率一样。
74 0
LeetCode 382. Linked List Random Node
|
索引
LeetCode 345. Reverse Vowels of a String
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
114 0
LeetCode 345. Reverse Vowels of a String
|
机器学习/深度学习 NoSQL
LeetCode 344. Reverse String
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
107 0
LeetCode 344. Reverse String