1. 原题链接
https://leetcode.com/problems/rotate-list/description/
2. 题目要求
给出一个链表的第一个结点head和正整数k,然后将从右侧开始数第k个结点之后的链表与之前的链表交换位置,例如
3. 解题思路
(1)首先要注意head结点不是指头结点,而是指第一个结点;
(2)当head为null或者链表中只有一个结点时,返回head;
(3)个人觉得题目出的很不友好,当k=链表的长度时,返回的时原链表;当k大于链表的长度时,则不是。。。无法理解。因此我按照自己的思路,默认当k大于链表长度时,依然返回原链表。
(4)具体解决思路:首先引入一个头指针指向第一个结点,然后再引入两个指针first和second指针。first先于second向前移动k个结点,然后first和second同步向后移动,直到尾结点。
4. 代码实现
public class RotatedList61 { public static void main(String[] args) { ListNode head = new ListNode(1); ListNode l2 = new ListNode(2); ListNode l3 = new ListNode(3); ListNode l4 = new ListNode(4); ListNode l5 = new ListNode(5); head.next = l2; l2.next = l3; l3.next = l4; l4.next = l5; l5.next = null; ListNode l = rotateRight(head, 7); do { System.out.println(l.val); l = l.next; } while (l != null); } public static ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null) return head; ListNode headPoint = new ListNode(0); ListNode first = headPoint; ListNode second = headPoint; headPoint.next = head; // first指针先移动k个结点 while (k > 0) { first = first.next; if (first.next == null) return head; k--; } // first、second同步向后移动 while (first.next != null) { first = first.next; second = second.next; } first.next = headPoint.next; headPoint.next = second.next; second.next = null; return headPoint.next; } } class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }