题目描述（中等难度）

给定链表的一个范围，将这个范围内的链表倒置。

解法一

首先找到 m 的位置，记录两端的节点 left1 和 left2 。 然后每遍历一个节点，就倒置一个节点。 到 n 的位置后，利用之前的 left1 和 left2 完成连接。 为了完成链表的倒置需要两个指针 pre 和 head。为了少考虑边界条件，例如 m = 1 的倒置。加一个哨兵节点 dummy。 1. m = 2, n = 4 2. 3. 1 2 3 4 5 加入哨兵节点 d，pre 简写 p，head 简写 h 4. 5. 0 1 2 3 4 5 往后遍历 6. ^ ^ 7. d h 8. p 9. 10. 0 1 2 3 4 5 此时 h 指向 m 的位置，记录 p 和 h 为 l1 和 l2 11. ^ ^ ^ 12. d p h 13. 14. 0 1 2 3 4 5 然后继续遍历 15. ^ ^ ^ 16. d p h 17. l1 l2 18. 19. 0 1 2 3 4 5 开始倒置链表，使得 h 指向 p 20. ^ ^ ^ ^ 21. d l1 p h 22. l2

当前状态用图形描述 倒转链表，将 h 的 next 指向 p，并且后移 p 和 h。 然后上边一步会重复多次，直到 h 到达 n 的位置。当然这道题比较特殊，上图 h 已经到达了 n 的位置。 此时，我们需要将 h 指向 p，同时将 l1 指向 h，l2 指向 h.next，使得链表接起来。 操作完成，将 dummy.next 返回即可。 1. public ListNode reverseBetween(ListNode head, int m, int n) { 2. if (m == n) { 3. return head; 4. } 5. ListNode dummy = new ListNode(0); 6. dummy.next = head; 7. int count = 0; 8. ListNode left1 = null; 9. ListNode left2 = null; 10. ListNode pre = dummy; 11. while (head != null) { 12. count++; 13. //到达 m，保存 l1 和 l2 14. if (count == m) { 15. left1 = pre; 16. left2 = head; 17. } 18. // m 和 n 之间，倒转链表 19. if (count > m && count < n) { 20. ListNode temp = head.next; 21. head.next = pre; 22. pre = head; 23. head = temp; 24. continue; 25. } 26. //到达 n 27. if (count == n) { 28. left2.next = head.next; 29. head.next = pre; 30. left1.next = head; 31. break; 32. } 33. //两个指针后移 34. head = head.next; 35. pre = pre.next; 36. } 37. return dummy.next; 38. }

时间复杂度：O（n）。 空间复杂度：O（1）。

总

考察链表知识，如果对链表很熟悉，在纸上画一画，理清楚怎么指向，很快可以写出来。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情