刷题_28：反转部分单向链表 and 猴子分桃

╰半橙微兮° 2023-09-30 22:14 3阅读 0赞

### 一.反转部分单向链表 ###

**题目链接：**

> [反转部分单向链表][Link 1]

**题目描述：**

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

**输入描述：**

> **n 表示单链表的长度。  
> val 表示单链表各个节点的值。  
> L 表示翻转区间的左端点。  
> R 表示翻转区间的右端点。**

**输出描述：**

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

**示例1：**

> **输入：  
> 5  
> 1 2 3 4 5  
> 1 3  
> 输出：  
> 3 2 1 4 5**

**示例2：**

> **输入：  
> 0,0  
> 输出：  
> 0**

**个人总结：**

> **定义一个单链表节点，然后构造单链表，再根据输入的l找到左端点和其前驱节点，根据r找到右端点和其后继节点，接着断开链表，翻转链表，最后在重新连接链表，按照顺序输出即可。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            //构造单链表
            int n = sc.nextInt();
            Node dummyHead = new Node(-1);
            Node tail = dummyHead;
            for (int i = 0; i < n; i++) {
        
                int val = sc.nextInt();
                tail.next = new Node(val);
                tail = tail.next;
            }
            int l = sc.nextInt();
            int r = sc.nextInt();
            //找到第l个节点和他的前驱节点
            Node pre = null;
            Node ln = dummyHead;
            while (l-- != 0) {
        
                pre = ln;
                ln = ln.next;
            }
            //找到第r个节点和他的后继节点
            Node rn = dummyHead;
            Node next = rn.next;
            while (r-- != 0) {
        
                rn = rn.next;
                next = rn.next;
            }
            //断开
            pre.next = null;
            rn.next = null;
            //逆置部分
            reverse(ln);
            //在链接上
            //逆置之后 rn为头 ln为尾
            pre.next = rn;
            ln.next = next;
            //打印
            Node tmp = dummyHead.next;
            while (tmp != null) {
        
                System.out.print(tmp.val + " ");
                tmp = tmp.next;
            }
        }
    
        public static Node reverse(Node head) {
        
            Node pre = null;
            Node next = null;
            while (head != null) {
        
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
    
        static class Node {
        
            int val;
            Node next;
    
            public Node() {
        
    
            }
    
            public Node(int val) {
        
                this.val = val;
            }
        }
    }

--------------------

### 二.猴子分桃 ###

**题目链接：**

> [猴子分桃][Link 2]

**题目描述：**

> **老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。  
> 第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。  
> 第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。  
> 后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。  
> 这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。**

**输入描述：**

> **输入包括多组测试数据。  
> 每组测试数据包括一个整数n(1≤n≤20)。  
> 输入以0结束，该行不做处理。**

**输出描述：**

> **每组测试数据对应一行输出。  
> 包括两个整数a，b。  
> 分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。**

**示例1：**

> **输入：  
> 5  
> 1  
> 0  
> 输出：  
> 3121 1025  
> 1 1**

**他人思路：**

> **纯数学题，思路与前面人的思路不太一样，不用借桃子，直接根据题意来进行求解，设最少需要桃子X个：  
> 第一次经过题目的处理剩余桃子数目为：4/5(X-1)=(4/5)*X-(4/5)；  
> 第二次剩余桃子个数为：4/5(4/5(X-1)-1)=((4/5)2)\*X-(4/5)2-(4/5)；  
> 第三次剩余桃子个数为：4/5(4/5(4/5(X-1)-1)-1)=((4/5)3)\*X-(4/5)3-(4/5)^2-(4/5)；  
> …  
> 依次类推，经过n只猴子的类似处理，剩余桃子数为：  
> 4/5(4/5(4/5(…(4/5(X-1)…)-1)-1)-1)=((4/5)n)\*X)-(4/5)n-(4/5)^(n-1)-…-(4/5)  
> =((4/5)n)\*X)-4\[1-(4/5)n\]  
> =(X+4)*(4/5)^n-4  
> 因此，同前人的推导一致，最终，只需要满足x+4的值为5^n次方则可以保证最后能得到一个整数，满足题目的要求。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
        
                int n = sc.nextInt();
                if (n != 0) {
        
                    System.out.print((long) Math.pow(5, n) - 4 + " ");
                    System.out.print((long) Math.pow(4, n) - 4 + n);
                }
                System.out.println();
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/f11155006f154419b0bef6de8918aea2
[Link 2]: https://www.nowcoder.com/questionTerminal/480d2b484e1f43af8ea8434770811b4a