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

92 反转链表 II

程序员文章站 2022-06-16 18:03:13
题目描述:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL方法1:主要思路:(1)直观的想,找出要反转的一段的链表的头一个结点的前一个结点,使用头插法,将该段链表中的结点,按照要反转的个数,逐个的向后遍历,将各个结点插入到前面;(2)注意借助辅助的头结点;...

题目描述:
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

方法1:
主要思路:
(1)直观的想,找出要反转的一段的链表的头一个结点的前一个结点,使用头插法,将该段链表中的结点,按照要反转的个数,逐个的向后遍历,将各个结点插入到前面;
(2)注意借助辅助的头结点;

/**
 * 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* dummy=new ListNode(0);//辅助的头结点
        dummy->next=head;
        ListNode* curNode=dummy;
        //找出要反转的链表段的前一个结点
        while(--m){
            --n;
            curNode=curNode->next;
        }  
        //对当前段使用头插法进行反转
        head=curNode;
        curNode=curNode->next;
        ListNode* tmpNode=NULL;
        //使用要反转的个数作为限制
        while(--n){
            tmpNode=curNode->next;
            curNode->next=tmpNode->next;
            tmpNode->next=head->next;
            head->next=tmpNode;
        }
        //释放内存
        head=dummy->next;
        delete dummy;
        return head;
    }
};

本文地址:https://blog.csdn.net/weixin_44171872/article/details/107286741