在不使用内置类和方法的情况下，如何在Java中按链表的k个节点左右移动元素？输入：A->B->C->D n=2(向右移动2(输出：C->D->A->B
public static void shiftListRight(LinkedList linkedList, int n)
{
if(head==null)
{
return null;
}
int k=1;
LinkedList tail=head;
while(tail.getNext()!=null)
{
++k;
tail=tail.getNext();
}
n%=k;
if(n==0)
return head;
int stepsToNewHead= k-n;
tail.setNext(head);
List newTail = tail;
while(stepsToNewHead-- >0)
{
newTail.setNext(newTail);
}
//Implement your code here
}
}
这是一个非常简单的算法，您必须使用三次for...each循环和swap方法。我给你举了一个array的例子，你可以很容易地将它转换为List。
// offs > 0 - shift to the right
public static void shift(int[] arr, int offs) {
offs %= arr.length;
offs = offs < 0 ? arr.length + offs : offs;
for (int i = 0, j = arr.length - 1; i < j; i++, j--)
swap(arr, i, j);
for (int i = 0, j = offs - 1; i < j; i++, j--)
swap(arr, i, j);
for (int i = offs, j = arr.length - 1; i < j; i++, j--)
swap(arr, i, j);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
输出：
int[] arr1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
System.out.println(Arrays.toString(arr1)); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
shift(arr1, 3);
System.out.println(Arrays.toString(arr1)); // [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]
System.out.println();
int[] arr2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
System.out.println(Arrays.toString(arr2)); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
shift(arr2, -3);
System.out.println(Arrays.toString(arr2)); // [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
根据您问题中的示例输入和输出，我想说您希望旋转链表中的元素，而不是移动它们。
以下是我对SO问题的实现，题为Java-在LinkedList中"旋转"对象-是LinkedList.addLast(LinkedList.removeFirst(((编程好还是坏？换句话说，下面的代码显示了该问题中提到的方法addFirst()、addLast()、removeFirst()和removeLast()。
public class LinkdLst {
private ListNode head;
public void addFirst(ListNode node) {
if (node != null) {
if (head == null) {
head = node;
}
else {
node.setNext(head);
head = node;
}
}
}
public void addLast(ListNode node) {
if (node != null) {
if (head == null) {
head = node;
}
else {
ListNode previous = head;
ListNode current = head.getNext();
while (current != null) {
previous = current;
current = current.getNext();
}
previous.setNext(node);
}
}
}
public ListNode removeFirst() {
ListNode removed;
if (head == null) {
removed = null;
}
else {
removed = head;
head = head.getNext();
}
return removed;
}
public ListNode removeLast() {
ListNode removed;
if (head == null) {
removed = null;
}
else {
ListNode previous = null;
ListNode current = head;
while (current.getNext() != null) {
previous = current;
current = current.getNext();
}
removed = current;
if (previous != null) {
previous.setNext(null);
}
else {
head = null;
}
}
return removed;
}
public String toString() {
StringBuilder sb = new StringBuilder();
ListNode current = head;
while (current != null) {
sb.append(current);
current = current.getNext();
}
return sb.toString();
}
public static void main(String[] args) {
LinkdLst list = new LinkdLst();
list.addLast(new ListNode('A'));
list.addLast(new ListNode('B'));
list.addLast(new ListNode('C'));
list.addLast(new ListNode('D'));
System.out.println(list);
for (int i = 0; i < 2; i++) {
list.addLast(list.removeFirst());
}
System.out.println(list);
for (int i = 0; i < 2; i++) {
list.addFirst(list.removeLast());
}
System.out.println(list);
}
}
class ListNode {
private char data;
private ListNode next;
public ListNode(char datum) {
data = datum;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode node) {
next = node;
}
public String toString() {
return String.format("%c-> ", data);
}
}
首先，我根据你问题中的样本创建列表。然后我把它们旋转2，也根据你问题中的样本得到想要的结果。然后我旋转"；"旋转"；在相反的方向上用2列出；"旋转"；列表的原始顺序。以下是运行上述代码时的输出。
请注意，上面代码中的toString()方法仅用于调试目的，而不是实现的解决方案的一部分。换句话说，您可以安全地移除它们。
A-> B-> C-> D->
C-> D-> A-> B->
A-> B-> C-> D->