ITKeyword,专注技术干货聚合推荐

注册 | 登录

算法和数据结构面试题(16)-单链表倒置

qhshiniba 分享于 2014-12-29

推荐:算法与数据结构面试题(10)-颠倒链表

题目 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。 解题思路 1.先用递归颠倒 2.尝试不用递归颠倒 代码 1.递归式 public class Problem8

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

题目


链表操作
(1)单链表就地逆置

解题思路


关于单链表


1.创建单链表,需要首先写一个单链表的类。


推荐:算法和数据结构面试题(15)-8张扑克的游戏

题目 有4 张红色的牌和4 张蓝色的牌,主持人先拿任意两张,再分别在A、B、C 三人额头上贴任意两张牌,A、B、C 三人都可以看见其余两人额头上的牌,看完后让他

模仿LinkedList写一个SingleLinkedList类。


/**
 * Copyright 2014 TJ SPREADTRUM TEST_AF All Right Reserved
 *
 * @author: hui.qian Created on 2014年12月29日 下午4:55:41 Description:
 * @param <E>
 */
public class SingleLinkedList<E> extends AbstractSequentialList<E> implements
        List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 单链表的大小.transient表示该属性不能被序列化.
    transient int size = 0;
    // 第一个结点
    transient SingleNode<E> first;
    // 最后一个结点
    transient SingleNode<E> last;

     static class SingleNode<E> {
        E item;
        SingleNode<E> next;

        SingleNode(E element, SingleNode<E> next) {
            this.item = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return "SingleNode{" +
                    "item=" + item +
                    '}';
        }
    }

    public SingleLinkedList() {
    }

    /**
     * 通过集合创建单链表
     */
    public SingleLinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    // 向链表中添加元素
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 将e添加到链表的第一个位置
     */
    @Override
    public void addFirst(E e) {
        // TODO Auto-generated method stub
        linkFirst(e);
    }

    /**
     * 将e添加到链表的最后一个位置
     */
    @Override
    public void addLast(E e) {
        // TODO Auto-generated method stub
        linkLast(e);
    }


    /**
     * 链接第一个节点
     * @param e
     */
    private void linkFirst(E e) {
        SingleNode<E> f = first;
        SingleNode<E> newElement = new SingleNode<E>(e, f);
        first = newElement;
        if (f == null) {
            last = newElement;
        }
        // 链表的结点个数+1
        size++;
        // 对链表修改的次数+1
        modCount++;
    }

    @Override
    public boolean offerFirst(E e) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean offerLast(E e) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public E removeFirst() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E removeLast() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E pollFirst() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E pollLast() {
        // TODO Auto-generated method stub
        return null;
    }

    /**
     * 得到链表中的第一个元素
     */
    @Override
    public E getFirst() {
        // TODO Auto-generated method stub
        SingleNode<E> f = first;
        if (f == null)
            throw new NoSuchElementException();

        return f.item;
    }
    public SingleNode<E> getFirstNode() {
        // TODO Auto-generated method stub
        SingleNode<E> f = first;
        if (f == null)
            throw new NoSuchElementException();

        return f;
    }

    @Override
    public E getLast() {
        final SingleNode<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
    public SingleNode<E> getLastNode() {
        final SingleNode<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l;
    }

    private E unlinkFirst(SingleNode<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final SingleNode<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        size--;
        modCount++;
        return element;
    }

    @Override
    public E peekFirst() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E peekLast() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public boolean removeFirstOccurrence(Object o) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean removeLastOccurrence(Object o) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean offer(E e) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public E remove() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E poll() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E element() {
        // TODO Auto-generated method stub
        return getFirst();
    }
    /**
     * 查询第一个元素
     */
    @Override
    public E peek() {
        // TODO Auto-generated method stub
        final SingleNode<E> f = first;
        return (f == null) ? null : f.item;
    }

    @Override
    public void push(E e) {
        // TODO Auto-generated method stub

    }
    /**
     * 获得链表第一个元素,并从链表中移除该结点
     */
    @Override
    public E pop() {
        final SingleNode<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    @Override
    public Iterator<E> descendingIterator() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    /**
     * 链表的元素大小
     * @return
     */
    @Override
    public int size() {
        // TODO Auto-generated method stub
        return size;
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 根据索引值得到结点
     */
    SingleNode<E> node(int index) {
        // assert isElementIndex(index);
        // >>位运算,size向右移动一位
        SingleNode<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    }

    void linkLast(E e) {
        final SingleNode<E> l = last;
        final SingleNode<E> newNode = new SingleNode<E>(e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        SingleNode<E> pred = null, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked")
            E e = (E) o;
            SingleNode<E> newNode = new SingleNode<E>(e, null);
            if (pred == null) {
            } else {
                pred.next = newNode;
            }
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;

        }

        size += numNew;
        modCount++;
        return true;
    }

    @Override
    public String toString() {
        return "SingleLinkedList{" +
                "size=" + size +
                ", first=" + first +
                ", last=" + last +
                '}';
    }
}



测试程序


public class Problem24 {

    public static void main(String[] args){
        Random random = new Random();

        SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
        //初始化单向链表
        for(int i=0;i<10;i++){
            int value = random.nextInt(10);
            list.add(value);
        }
        //颠倒链表
        SingleLinkedList.SingleNode<Integer> firstNode = list.getFirstNode();
        SingleLinkedList.SingleNode<Integer> currentNode = firstNode;
        SingleLinkedList.SingleNode<Integer> beforeNode = null;
        while(currentNode!=null&&currentNode.next!=null){
            SingleLinkedList.SingleNode<Integer> nextNode = currentNode.next;
            currentNode.next = beforeNode;
            beforeNode = currentNode;
            currentNode = nextNode;
        }
        firstNode = list.getFirstNode();
        System.out.println("Done!"+list.getLast());
    }
}


推荐:单链表的反转(数据结构 面试题)

编写一个算法来颠倒一个链表,该链表的第一个结点由first指向。不要复制列表元素;而是重置链接和指针,使得first指向原来的最后一个结点,并且结点之间的所有链

题目 链表操作(1)单链表就地逆置 解题思路 关于单链表 1.创建单链表,需要首先写一个单链表的类。 模仿LinkedList写一个SingleLinkedList类。 /** * Copyright 2014 TJ SPREADTRUM TEST_AF

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。