题解 | #MP3光标位置#

import java.util.*;

// 注意链表与linkedlist先进先出队列的使用
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int num = scanner.nextInt();
            String s = scanner.next();
            String[] split = s.split("");
            SingleLinkList sLt = new SingleLinkList();
            int head=1;
            sLt.insert(head);//新建链表，存放head与next，初始头下标为1
            for (int i = 2; i <=num ; i++) {
                sLt.insert(i);
            }
            LinkedList<Integer> it = new LinkedList<>();
            it.add(1);
            it.add(2);
            it.add(3);
            it.add(4);
//            System.out.println(it);
            int dnow=1;
            for (int i = 0; i < split.length; i++) {
                if (dnow==1&&split[i].equals("U")){
                    it.clear();
                    it.add(num-3);
                    it.add(num-2);
                    it.add(num-1);
                    it.add(num);
                } else if (dnow==num&&split[i].equals("D")) {
                    it.clear();
                    it.add(1);
                    it.add(2);
                    it.add(3);
                    it.add(4);
                }else {
                    if (dnow==it.get(3)&&split[i].equals("D")){
                        it.remove();
                        it.add(dnow+1);
                    } else if (dnow==it.get(0)&&split[i].equals("U")) {
                        it.clear();
                        it.add(dnow-1);
                        it.add(dnow);
                        it.add(dnow+1);
                        it.add(dnow+2);
                    }
                }
                int reback = reback(split[i], num, dnow);
//                System.out.println("下标为"+i1);
                Integer byIndex = sLt.getByIndex(reback);
                dnow=byIndex;

            }
            for (int i = 0; i < it.size(); i++) {
                if (it.get(i)>0) {
                    System.out.print(it.get(i) + " ");
                }
            }
            System.out.println();
            System.out.println(dnow);
        }
    }
    public static int reback(String split,int num,int denow){
        int index=0;

        if (split.equals("U")){
            index=index-1;
        }else if (split.equals("D")){
            index=index+1;
        }

        denow=denow+index;
        if(denow>num){
            denow=denow-num;
        }else if (denow<=0){
            denow=num+denow;
        }
        return denow;
    }
}

class LinkListNode {
    private Integer data; // 结点的数据域

    private LinkListNode next; // 下一个结点

    public LinkListNode(){
    }

    public LinkListNode(Integer data){
        this.data = data;
        this.next = null;
    }
    public LinkListNode(Integer data,LinkListNode next){
        this.data = data;
        this.next = next;
    }

    public Integer getData() {
        return data;
    }

    public void setData(Integer data) {
        this.data = data;
    }

    public LinkListNode getNext() {
        return next;
    }

    public void setNext(LinkListNode next) {
        this.next = next;
    }
}

class SingleLinkList {

    private LinkListNode head;//定义单链表的头结点

    private int length;//用来记录单链表的长度

    /**
     * 单链表的初始化 init() 无参
     */
    public SingleLinkList(){
        this.head = new LinkListNode();
    }

    /**
     * 单链表的初始化 init() 有参
     * */
    public SingleLinkList(Integer data,LinkListNode next){
        this.head = new LinkListNode();
        LinkListNode node = new LinkListNode();
        node.setData(data);
        node.setNext(next);
        head.setNext(node);
    }

    /**
     * 求单链表长度
     */
    public int getLength(){
        return length;
    }

    /**
     * 新增：默认在最后插入一个数据元素；
     */
    public LinkListNode insert(Integer data){
        LinkListNode newNode = new LinkListNode(data);
        LinkListNode p = head;
        while (p.getNext()!=null){
            p = p.getNext();
        }
        p.setNext(newNode);
        length++;
        return newNode;
    }

    /**
     * 新增：在位置i插入一个数据元素；
     */
    public void insertByIndex(int index,Integer data){
        // 如果位置i大于了单链表的长度 或者 位置不合理 则直接将新结点添加到最后
        if(index>length||index-1<0){
            insert(data);
            return;
        }
        index--;
        // 将指针p指向首元结点
        LinkListNode p = head;//head首元节点永远是链表中的末尾最后一个
        while (index!=0){
            p=p.getNext();
            index--;
        }
        LinkListNode newNode = new LinkListNode(data,p.getNext());
        p.setNext(newNode);
        length++;
    }

    /**
     * 查找：按位置查找
     */
    public Integer getByIndex(int index){
        // 如果查找的元素大于了单链表的长度则返回null
        if(index>length){
            return null;
        }
        // 将指针p指向头结点
        LinkListNode p = head;
        while (index!=0){
            p=p.getNext();
            index--;
        }
        return p.getData();
    }

    /**
     * 查找：按值查找
     */
    public int getByData(Integer data){
        // 将指针p指向首元结点
        LinkListNode p = head;
        int index = 0;
        while (p.getNext()!=null){
            p=p.getNext();
            index++;
            if(p.getData().equals(data)){
                return index;
            }
        }
        if(index==length&&!p.getData().equals(data)){
            return 0;
        }
        return index;
    }

    /**
     * 查找：遍历单链表
     */
    public ArrayList<Integer> traverse(){
        LinkListNode p = head;
        ArrayList<Integer> it = new ArrayList<>();
        while (p.getNext()!=null){
            p = p.getNext();
            it.add(p.getData());
        }
        return it;
    }

    /**
     * 删除：按位置i删除数据元素；
     */
    public Integer deleteByIndex(int index){
        // 如果位置i大于了单链表的长度则返回null
        if(index>length||index-1<0){
            return null;
        }
        // 提前将index-- 是为了将p指针移到被删除元素的前一个位置
        index--;
        // 将指针p指向头结点
        LinkListNode p = head;
        while (index!=0){
            p=p.getNext();
            index--;
        }
        int res = p.getNext().getData();
        p.setNext(p.getNext().getNext());
        length--;
        return res;
    }

    /**
     * 合并链表
     */
    public void marge(SingleLinkList singleLinkList){
        LinkListNode p = head;
        length=length+singleLinkList.length;
        while (p.getNext()!=null){
            p = p.getNext();
        }
        p.setNext(singleLinkList.head.getNext());
    }
}