leetcode61-Rotate List

题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

分析

这道题目用快慢指针即可解，先快指针往前走k个位置，然后和慢指针同时开始遍历，直到快指针的next为空。这个时候慢指针的next就是最新的头结点。这里要注意k比链表总长度大的情况，可以通过求余解决

public class LinkNode {
	int val;
	LinkNode next;

	public LinkNode(int data) {
		this.val = data;
		this.next = null;
	}
}
public class LinkList {
	LinkNode head;
	public LinkList() {
		this.head = null;
	}
	public LinkNode getHead() {
		return this.head;
	}
	//添加元素
	public void addNode(int data) {
		LinkNode node = new LinkNode(data);
		if (this.head == null) {
			this.head = node;
		} else {
			LinkNode cur = this.head;
			while(cur.next != null) {
				cur = cur.next;
			}
			cur.next = node;
		}
	}
	//正序打印
	public void print(LinkNode node) {
		while(node != null) {
			System.out.print(node.val);
			System.out.print(" ");
			node = node.next;
		}
		System.out.println();
	}
	public void rotate(int k) {
		if(this.head == null) {
			return;
		}
		LinkNode p = this.head;
		int cnt = 0;
		while(p!= null) {
			cnt++;
			p = p.next;
		}
		k = k % cnt;
		LinkNode fast = this.head;
		LinkNode slow = this.head;
		for(int i = 0;i<k;i++) {
			fast = fast.next;
		}
		while(fast.next != null) {
			fast = fast.next;
			slow = slow.next;
		}
		fast.next = head;
		fast = slow.next;
		slow.next = null;
		print(fast);
	}
}

public class rotateList {
	public static void main(String[] args) {
		LinkList list = new LinkList();
		list.addNode(1);
		list.addNode(2);
		list.addNode(3);
		list.addNode(4);
		list.addNode(5);
		list.rotate(2);
	}
}