题目
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码
public class DayCode { public static void main(String[] args) {
} /** * https://leetcode-cn.com/problems/reverse-linked-list-ii/ * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param left * @param right * @return */ public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(-1); dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < left - 1; i++) { pre = pre.next; }
ListNode rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; }
ListNode leftNode = pre.next; ListNode cur = rightNode.next;
pre.next = null; rightNode.next = null;
reverse(leftNode);
pre.next = rightNode; leftNode.next = cur; return dummy.next; }
/** * 翻转链表 * * @param root */ public void reverse(ListNode root) { ListNode pre = null; ListNode current = root; while (current != null) { ListNode next = current.next; current.next = pre; pre = current; current = next; } }}
复制代码
总结
评论