首页 > 代码库 > [C++]LeetCode: 62 Reverse Linked List II

[C++]LeetCode: 62 Reverse Linked List II

2024-10-18 19:52:02   213人阅读

题目：

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.

插入法

思路：

Step 1：找到m结点所在的位置，并维护m结点前一个节点p，以便之后一直在此处插入。

Step 2： 进行反转直到n结点。反转方法是每次读到一个节点，把它插入到当前链表m结点的前一个位置（p->next）,然后原m节点接到读到的节点的下一个。

复杂度：O(N)，需要几个辅助指针，空间O(1)

Attention:

1. 插入时一定是插入当前m节点的前一个位置，即之前维护的p节点下一个位置。

tmp->next = p->next;   //此处一定要是p->next，因为每次插入都是在m的前一个位置，p之后第一个位置。
2. 注意头结点和第一个节点的初始化和定义方法（区别结点和链表）

ListNode dummyhead(0);
dummyhead.next = head;
ListNode* p = &dummyhead;

3.区分两种数据结构
节点由存放数据元素的数据域和存放后继结点地址的指针域组成。
ListNode* p;   若p是指向线性表第i个元素的指针。
p->next表示一个指针，指向下一个结点。
ListNode p(0); 若p是一个链表内的一个单独节点。
p.next表示一个值，即p节点内保存了另一个结点的地址信息。
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
AC Code:

/**
 * 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) {
        //插入法
        if(head == NULL) return NULL;
        ListNode dummyhead(0);
        dummyhead.next = head;
        ListNode* p = &dummyhead;
        
        for(int i = 1; i < m; i++)
        {
            p = p->next;
        }
        head = p->next;  //head即第m个结点, p为m前一个节点
        
        //执行插入
        for(; m < n; m++)
        {
            ListNode* tmp = head->next;
            head->next = tmp->next;
            tmp->next = p->next;   //此处一定要是p->next，因为每次插入都是在m的前一个位置，p之后第一个位置。
            p->next = tmp;  
        }
        
        return dummyhead.next;
    }
};



[C++]LeetCode: 62 Reverse Linked List II


联系
我们