题解 | #两个链表生成相加链表#

首先分析一波解题思路：

1. 找到需要翻转的链表段[1,2,3,4,5] 2,4 即2，3，4需要翻转

2. 保存翻转前面的链表[1]，保存翻转节点后面的节点[5]

3. 翻转需要翻转的链表段, 拼接前 + 翻转 + 后节点

   public ListNode reverseBetween (ListNode head, int m, int n) {
   
        //1.定义一个前驱链表
        ListNode prv = new ListNode(0);
        //2.实际操作的链表
        ListNode cru = prv;
        //将head赋值给他
        cru.next = head;
        //定义一个链表保存后节点
        ListNode last = null;
       //保存需要翻转后的链表
        ListNode revNode = null;
        //定义一个计数器 标记从哪里开始翻转
        int count = 1;
        while(cru!=null && cru.next!=null){
           //如果count == 2
           if(count == m){
                 //从前面截取[1,2,3,4,5] 此时前节点应该为1；
                 ListNode rev = cru.next;
                //定义一个临时链表保存开始翻转的链表[2,3,4,5]
                 ListNode temp = rev;
                //将前驱链表滞空
                 cru.next = null;
                 //定义计数器保存链表开始翻转到结束的长度n-m
                 int time = 0;
                 //链表一直下去
                 while(temp!=null && time < n-m){
                     temp=temp.next;
                     time++;
                }
                //此时last == [5]
                last  = temp.next;
                //此操作将rev=[2,3,4,5] -> rev[2,3,4]
                temp.next= null;   
                //翻转[2,3,4] 并把后节点拼到翻转后的节点后面
                revNode=rever(rev,last);
               //将翻转后的节点赋值给cru.next;
                cru.next=revNode;
                break;
             }   
            else{
            //不相等继续遍历 
            cru = cru.next; 
           //计数+1
            count++;
        }
     }
      return prv.next;
    }
    ListNode rever(ListNode head,ListNode last){
       //翻转链表
        ListNode prv = new ListNode(0);
        ListNode cru = prv;
        //定义一个栈先进后出 
        Stack<ListNode> stack = new Stack<>();
        while(head!=null){
            ListNode temp = head.next;
            head.next = null;
            stack.push(head);
            head = temp;
        }
        //循环出栈，即反转
         while(!stack.isEmpty()){
             ListNode pk = stack.pop();
             cru.next = pk;
             cru = cru.next;
         }  
         //把last节点拼到翻转节点后面
         cru.next = last;
         return prv.next;
    }