1 题目
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
2 解答
先找到第一个反转节点的前一个节点，（前一个节点就当作头，对后边的范围元素进行头插法），如果是第一个节点开始的话，那么它没头节点，就创建一个新节点，来当做头节点：
/** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { /** * @param head: ListNode head is the head of the linked list * @param m: An integer * @param n: An integer * @return: The head of the reversed ListNode */ public ListNode reverseBetween(ListNode head, int m, int n) { // write your code here if (head == null) return head; // 基本思路：找到开始反转的第一个节点，然后采用头插法依次插入即可实现反转 ListNode resNode = head, preNode = head; // 找到开始反转的前一个节点 for (int i = 1; i < m - 1; i++) { preNode = preNode.next; } // 如果从第一个节点开始反转，创建一个节点，方便进行头插 if (m == 1) { preNode = new ListNode(0); preNode.next = head; } // 从第一个节点开始 ListNode startNode = preNode.next; // 因为从第一个节点，只需要把第一个节点的后边节点都插入到前边来 // 所以是 m - n 次循环 for (int i = m; i < n; i++) { // 第一个节点的下一个节点 ListNode nextNode = startNode.next; // 把第一个节点指向下一个节点的下一个节点 startNode.next = nextNode.next; // 下一个节点的下一个节点指向头节点的下一个节点 nextNode.next = preNode.next; // 头节点的下一个节点指向下一个节点 preNode.next = nextNode; } // 是从第一个节点开始的，就返回我们创建的头节点的下一个节点 // 不是的话就返回原来的头节点 return m == 1 ? preNode.next : resNode; } }
还有我刚开始写的一个，自己把自己绕进去了，还没实现，千万别看我下边这个，这里仅记录，给自己留个纪念。。。。。
public class Solution { /** * @param head: ListNode head is the head of the linked list * @param m: An integer * @param n: An integer * @return: The head of the reversed ListNode */ public ListNode reverseBetween(ListNode head, int m, int n) { // write your code here if (head == null) return head; // 要反转的起始的前一个节点、结束节点 // 当 m = 1 的时候，是从第一个节点开始反转的，那么 preStartNode 指向 head ListNode resNode = head, preStartNode, endNode; // 计数器 int num = 1; ListNode iteratorHead = head; while (iteratorHead != null) { if (num == m - 1) { preStartNode = head; } if (num == n) { endNode = head; break; } // 指向下一个节点 iteratorHead = iteratorHead.next; num++; } // 开始进行反转 // 先把 endNode 节点的next保留下 ListNode endNodeNext = endNode.next; // 处理下 preStartNode if (preStartNode == null) { preStartNode = new ListNode(0); } // 要迭代几次 int total = n - m + 1; ListNode startStartNode = startNode.next; while (total > 0) { startStartNode endNode.next = startStartNode; preStartNode.next = endNode; if (total == 1) { } total--; } return m == 1 ? preStartNode.next : resNode; } }
加油。