算法通关村第二关——指定区间反转问题

指定区间反转：

Leetcode92有这样一道题：给你单链表的头指针head和两个整数left、right，其中left<=right，请你反转从位置left到位置right的链表结点，返回反转后的链表，如图所示：

这道题呢，有两种不同的解法，分别是头插法和穿针引线法，头插法就是我们前面说过的带头结点的反转，而穿针引线法就是不带头结点实现反转的方法，接下来我将逐一介绍：

1.头插法： 

前面我们说过带头结点的反转有两个重点要求：1.虚拟头结点  2.拆拆拆

熟练掌握以上两个思想后，这道题的解决将变得十分简单。在这道题中，我认为我们可以将区间前的第一个结点看作虚拟头结点，而区间内除第一个结点以外的全部结点则需要逐一拆除并进行插入，如下图所示：

我们可以建立一个cur指针始终指向区间的第一个元素，之后的每一步操作我们需要以下几个步骤：1.找到当前结点的下一个结点 2.拆除：令cur指针指向的结点指向next结点的下一个结点（即：将next指针指向的结点“拆下”，并保存后一个结点的位置）3.插入： 令next指针指向的结点指向虚拟头结点的下一个结点（这里的虚拟头结点就是我们说的区间前的第一个结点） 4：令虚拟头结点指向next指针所指向的结点。重复上述操作，即可实现区间反转，代码如下：

1.  
   // 头插法
2.  
   struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
3.  
   {
4.  
   struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟一个虚拟的头结点
5.  
   dummy->val = -1;
6.  
   dummy->next = head;//令虚拟头结点的下一个结点指向真实头结点
7.  
   struct ListNode* ans = dummy;//创建一个指针用来遍历链表
8.  
   for (int i = 0; i < left - 1; i )
9.  
   {
10.  
    ans = ans->next; //找到指定区间的前一个元素
11.  
    }
12.  
    struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode));
13.  
    cur = ans->next;//令cur为区间的第一个结点，并始终保持不变
14.  
    for (int i = 0; i < right - left; i )//遍历整个区间
15.  
    {
16.  
    struct ListNode* next = cur->next;//首先找到当前结点的下一个结点
17.  
    cur->next = next->next;//令当前结点的下一个结点指向下一个结点所指向的结点，即将next结点“拆下”
18.  
    next->next = ans->next;//令next结点的下一个结点指向区间前的结点所指向的结点
19.  
    ans->next = next;//令区间前的结点指向next结点
20.  
    }
21.  
    return dummy->next;
22.  
    }

2.穿针引线法：

如果说第一种方法的特点是拆拆拆，那这一种方法的特点就类似于从整体上解决问题的方法，让我们先从图片中了解大致思想：

这种方法呢，其实就是将整个区间先与原链表脱离，单独将区间反转之后再接入原链表，步骤如下：1.找到区间的前驱结点与后续结点，便于之后进行连接 2.定位区间的左结点与右结点 3.将整个区间拆下 4.对区间进行反转 5.将反转后的区间接入旧链表，代码如下：

1.  
   //反转链表
2.  
   void reverseList(strruct ListNode* head)
3.  
   {
4.  
   sturct ListNode* pre = NULL;
5.  
   struct ListNode* cur = head;
6.  
   while (cur != NULL)
7.  
   {
8.  
   struct ListNode* next = cur->next;
9.  
   cur->next = pre;
10.  
    pre = cur;
11.  
    cur = next;
12.  
    }
13.  
     
14.  
    }
15.  
    //穿针引线法
16.  
    struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
17.  
    {
18.  
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
19.  
    dummy->val = -1;
20.  
    dummy->next = head;
21.  
    struct ListNode* pre = dummy;
22.  
    for (int i = 0; i < left - 1; i )
23.  
    {
24.  
    pre = pre->next;//首先找到区间的前一个结点
25.  
    }
26.  
    struct ListNode* rightNode = pre;
27.  
    for (int i = 0; i < right - left 1; i )
28.  
    {
29.  
    rightNode = rightNode->next;//令该结点指向区间的最后一个结点
30.  
    }
31.  
    struct ListNode* leftNode = pre->next;//找到区间的第一个结点
32.  
    struct ListNode* succ = rithtNode->next;//找到区间之后的第一个结点
33.  
    rightNode->next = NULL;
34.  
    pre->next = NULL;//断开区间链表与原链表的链接
35.  
    reverseList(leftNode);//将区间内的链表进行反转
36.  
    pre->next = rightNode;//令之前保存的区间前的第一个结点指向此时链表的头结点
37.  
    leftNode->next = succ;//令链表的尾结点指向之前保存的区间之后的第一个结点
38.  
    return dummy->next;
39.  
    }

这篇好文章是转载于：学新通技术网