dabocaiqq
2020-04-13 16:16
采纳率: 66.6%
浏览 125

Java语言高分悬赏:如何颠倒一个双向链表,写出具体的实现代码,并且注释下你的代码

Java语言高分悬赏:如何颠倒一个双向链表,写出具体的实现代码,并且注释下你的代码

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • 毕小宝 2020-05-06 11:46
    已采纳

    这里有一篇详细的介绍,问答贴代码不太好阅读,直接参考这篇吧:
    https://blog.csdn.net/lwkrsa/article/details/82015364

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • dugusha0421 2020-04-13 16:20

    public class DoubleLinkedListTest {

    /**
     * 链表打印
     *
     * @param list
     */
    public static void printDoubleLinkedList(DoubleLinkedList<Integer> list) {
        StringBuffer sb = new StringBuffer();
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            sb.append(it.next());
            if(it.hasNext()) {
                sb.append("->");
            }
        }
        System.out.println(sb.toString());
    }
    
    public static void main(String[] args) {
    
        DoubleLinkedList<Integer> list = new DoubleLinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
    
        System.out.println("链表倒置前:");
        printDoubleLinkedList(list);
    
        list.reverse();
    
        System.out.println("链表倒置后:");
        printDoubleLinkedList(list);
    }
    

    }
    public class DoubleLinkedList {

    transient Node<E> first; //头节点
    transient Node<E> last; //尾节点
    transient int size = 0; //节点个数
    
    public DoubleLinkedList() {
    }
    
    /**
     * 判断是否为空
     *
     * @return true 为空, false 不为空
     */
    public boolean isEmpty() {
        return 0 == size;
    }
    
    /**
     * 获取表元素个数
     *
     * @return 表链元素个数
     */
    public int size() {
        return size;
    }
    
    /**
     * 反序排列列表中的值
     */
    public void reverse() {
        if (isEmpty()) {
            return;
        }
        // 表的头节点与尾节点互换位置
        Node<E> temp = first;
        first = last;
        last = temp;
    
        // 从表头按序遍历 更每个新节点的前后节点互换
        Node<E> n = first;
        while (n != null) {
            temp = n.next;
            n.next = n.per;
            n.per = temp;
            n = n.next;
        }
    }
    
    /**
     * 根据索引获取元素
     *
     * @param index 元素
     * @return
     */
    public E get(int index) {
        checkIndex(index);
        return getNode(index).item;
    }
    
    /**
     * 将元素追加到列表的末尾
     *
     * @param item 元素
     */
    public void add(E item) {
        Node<E> l = last;
        Node<E> newNode = new Node(l, item, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }
    
    /**
     * 根据索引获取节点
     *
     * @param index 索引
     * @return 节点
     */
    private Node<E> getNode(int index) {
        if (index < (size >> 2)) { //如果索引在列表前面 正序遍历
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { //否则倒叙遍历
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.per;
            }
            return node;
        }
    }
    
    /**
     * 检查索引值
     *
     * @param index 索引
     */
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
    
    /**
     * 节点元素
     *
     * @param <E>
     */
    private class Node<E> {
        E item;//元素的值
        Node per;// 前一个结点
        Node next;// 后一个结点
    
        public Node(Node per, E item, Node next) {
            this.item = item;
            this.per = per;
            this.next = next;
        }
    
        public String toString() {
            return item + "";
        }
    }
    
    /**
     * 自定义个一个列表迭代器
     *
     * @return
     */
    public Iterator<E> iterator() {
        return new Itr();
    }
    
    private class Itr implements Iterator<E> {
    
        int cursor = 0;
        int lastRet = -1;
    
        public boolean hasNext() {
            return cursor != size();
        }
    
        public E next() {
            try {
                E next = get(cursor);
                lastRet = cursor++;
                return next;
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
    
        public void remove() {
            if (-1 == lastRet) {
                throw new IllegalStateException();
            }
            throw new RuntimeException("remove is denied");
        }
    }
    

    }

    评论
    解决 无用
    打赏 举报
  • qq_26968845 2020-04-13 16:27
    评论
    解决 无用
    打赏 举报
  • BMKB 2020-04-22 18:31

    https://www.cnblogs.com/acm-bingzi/p/alibaba-linkedlist-reversed.html 实现一个双向列表倒置功能 内部还有项目源码

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题