java - 顺时针旋转链表

Question

我想将链接列表顺时针旋转一定的量。

 private class Node {

    private T data; // Entry in bag
    private Node next; // link to next node

    private Node(T dataPortion) {
        this(dataPortion, null);
    } // end constructor

    private Node(T dataPortion, Node nextNode) {
        data = dataPortion;
        next = nextNode;
    } // end constructor
} // end Node

public void leftShift(int num){

    if (num == 0) return;

    Node current  = firstNode;

    int count = 1;
    while (count < num && current !=  null)
    {
        current = current.next;
        count++;
    }

    if (current == null)
        return;


    Node kthNode = current;


    while (current.next != null)
        current = current.next;



    current.next = firstNode;


    firstNode = kthNode.next;


    kthNode.next = null;

}

我设法让逆时针旋转工作，但我对如何获得顺时针旋转有点困惑，因为我找不到以前的节点。

Answer 1

你问的例子:

    private class Node {

    private T data; // Entry in bag
    private Node next; // link to next node

    public Node(T dataPortion) {
        this(dataPortion, null);
    } // end constructor

    public Node(T dataPortion, Node nextNode) {
        data = dataPortion;
        next = nextNode;
    } // end constructor
  T getObject() {
    return data; 
  }
  Node<T> getNext() {
    return next; 
  }
} // end Node

public class Queue<T>{
 
    private Node head;
    private Node tail;
    private String name;


    public Queue(){
        this("queue");
    }
 
    public Queue(String listName) {
        name = listName;
        head = tail = null;
    }

    public boolean isEmpty() {
        return tail == null; 
    }

    public void put(T item) {
        Node node = new Node(item);

        if (isEmpty()) // head and tail refer to same object
            head = tail = node;
        else { // head refers to new node
            Node oldtail= tail;
            tail=node;
            oldtail.nextNode=tail;

        }
    }

    public Object get() throws NoSuchElementException {
        if (isEmpty()) // throw exception if List is empty
            throw new NoSuchElementException();
 
        T removedItem = head.data; // retrieve data being removed
 
        // update references head and tail
        if (head == tail)
            head = tail = null;
        else // locate new last node
        {
            head=head.nextNode;


        } // end else
 
        return removedItem; // return removed node data
    }
    public int size() {
      int count = 0;
      if(isEmpty()) return count;
      else{
        Node<T> current = head;

        // loop while current node does not refer to tail
        while (current != null){
            count++;
            if(current.nextNode==null)break;
            current=current.nextNode;
        }

        return count;
    }
    public void shift(){
      if(size()<=1)return;

      T removed = get();
      put(removed);
    }
}