【编程题 】 CD108 反转部分单向链表（详细注释 易懂）

题目描述

题目链接：     反转部分单向链表_牛客题霸_牛客网 (nowcoder.com)

 给定一个单链表，在链表中把第 L 个节点到第 R 个节点这一部分进行反转。

输入描述：

n 表示单链表的长度。

val 表示单链表各个节点的值。

L 表示翻转区间的左端点。

R 表示翻转区间的右端点。

输出描述：

在给定的函数中返回指定链表的头指针。

示例1

输入：

5
1 2 3 4 5
1 3

输出：

3 2 1 4 5

备注：

1≤n≤1000000
 1≤L≤R≤n
1000000−1000000≤val≤1000000

题意理解：

    给定一个单链表，在指定区间进行反转。这道题牛客网上，写着 入门题，但其实难度在四星，这个题属于是上下限比较大的一个题。 就是说，它题目要求的是单链表反转，但其实它什么也没有给你，你需要自己定义单链表结构，自己把它输入的每个数字放到一个 链表节点里，然后通过定义的的 next指针，把每个节点链接起来，形成单链表，然后你把这个单链表的头节点，还有 要反转的区间 传给 反转函数，进行反转，然后把反转后的 头节点传回来，最后让头节点，遍历传回来的 链表，打印输出。 

     为什么说这个题，上下限很大，因为，题目什么也没给，那不用链表做也可以，就用数组或者其他数据结构直接做，容易很多，代码也很简单，只要输出符合要求，它的运行时间和内存，与用链表做出来的是一样的。

解题思想：

    解题思想，上面题意理解基本上说完了，重点说如何反转链表，反转一个区间链表，其实难度并不小，如果你是第一次做，一定会思考很长一段时间，在lettcode 上面，这道题难度属于中等。  光用嘴说，不太好理解，画个图吧！ 

   图中，黑色箭头是原有的箭头，红色箭头是为了反转修改的指向，能看到，总共有三个红色箭头，我们要反转的是 1，2，3 ，那根据图，反转有什么特点呢？ 首先 prev要置于 反转前的一个节点，因为它要确保反转区间前的一个节点，要指向 反转区间的尾节点。             其次，cur节点要置于 反转区间的第一个节点，因为它要确保 反转区间的头节点 指向 反转区间的尾节点之后一个节点，curNext节点则要 确保始终在cur 的下一个节点。

  要注意的是，反转时，不能用 curNext.next = cur，因为curNext 是一个动节点，它始终在要反转的那个节点上，而 cur节点由于要保持 反转区间的头节点指向区间后的第一个节点，所以它是不能动的。 这里我们是让 curNext 指向prev.next 的节点的，因为prev.next 始终是指向 要反转的节点的 前一个节点的 。具体看一下 下面反转代码的四行代码就明白了。

 

     这里有个与此题几乎一样的题目，但要求没这么多，可以看看链表内指定区间反转__牛客网 (nowcoder.com)

代码注释：

  

import java.util.*;
// 定义一个单链表
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
    // 实例一个头节点
        ListNode head = new ListNode(scan.nextInt());
      
          ListNode cur = head;
       // i从1 开始，把之后的每个输入值实例为一个节点，然后链接起来
        for(int i=1;i< n;i++){
         ListNode node  = new ListNode(scan.nextInt());
          cur.next =node;
          cur = cur.next;
        }
     // 对接收的反转区间 减1，使其与下标一致
        int L = scan.nextInt()-1;
        int R = scan.nextInt()-1;
         head = reverse(head,n,L,R);
   // 收到返回的 头节点，遍历打印
        while(head != null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
   // 反转函数
    public static ListNode reverse(ListNode head, int n,int L,int R){
    // 实例一个 傀儡节点
         ListNode dummy = new ListNode(-1);
         // 傀儡节点指向头节点
        dummy.next = head;
       // prev 指针置于 傀儡节点上
        ListNode prev = dummy;
    // cur 指针置于prev的下一个节点
        ListNode cur = prev.next;
       // 循环这两个指针，确保prev置于 反转区间的前一个节点，cur节点置于 反转区间的第一个节点
        for(int i=0;i
            cur =cur.next;
            prev = prev.next;
        }
        // 区间有几个，就反转几个 
        for(int i=L;i
             ListNode curNext = cur.next;
            cur.next = curNext.next;
           curNext.next = prev.next;
            prev.next = curNext;
            
        }
        return dummy.next;
    }
}