小挑战

“算法虐我千百遍，我待算法如初恋”；算法能力的提示是循序渐进的，坚持就是胜利；本专题分享一些链表的题目，希望跟各位看官老爷一起在枯燥的算法练习中，共同进步。

题目1

给你一个单向链表的头节点，你能将链表翻转之后返回吗？

public class Node {
    int value; 
    Node next;
}

题目2

给你一个双向链表的头节点，你能将链表翻转之后返回吗？

public class Node {
    int value; 
    Node next;
    Node pre;
}

题目3

你可以使用链表实现队列结构吗？

public class Node {
    int value; 
    Node next;
}

题目4

你可以使用链表实现栈结构吗？

public class Node {
    int value; 
    Node next;
}

题目5

你可以使用链表实现双端队列结构吗？

public class Node {
    int value; 
    Node next;
    Node pre;
}

---------------------- 我是优美的分割线----------------------

题目1

给你一个单向链表的头节点，你能将链表翻转之后返回吗？

public class Node {
    int value; 
    Node next;
}

参考题解：

public static Node reverse(Node head){
    Node next = null;
    Node pre = null;
    while(head!=null){
	next = head.next;
	head.next = pre;
	pre = head;
	head =next;
    }
    return pre;
}

怎么样，希望这个简单的小练习没有难倒你；本题不是很复杂，考验的是答题者的编码能力和细心，相信经过梳理之后，你也可以很熟练的翻转。

题目2

给你一个双向链表的头节点，你能将链表翻转之后返回吗？

public class Node {
    int value; 
    Node next;
    Node pre;
}

参考题解：

public static Node reverse(Node head){
    Node next = null;
    Node pre = null;
    while(head!=null){
       next = head.next;
       head.next = pre;
       head.pre = next;
       pre = head;
       head = next;
    }
    return pre;
}

本题目与翻转单向链表类似；但是需要注意的是双向链表翻转时需要将当前节点的pre 节点的指针也做改变。

题目3

你可以使用链表实现队列结构吗？入队与出队都是O(1)的时间复杂度。

public class Node<V> {
    V value; 
    Node<V> next;

    public Node(V value){
       this.value =value;
    }
}

参考题解：

public class Queue<V> {

        Node<V> head;
        Node<V> tail;
        int size;

        public Queue(){
            size = 0 ;
            head = null ;
            tail = null ;
        }

        public void add(V data){
            Node node = new Node(data);
            if(head == null || tail == null){
                head = node;
                tail = node;
            }else{
                tail.next = node;
                tail = tail.next;
            }
            size++;
        }

        public V pop(){
            V result = null;
            if(head == null || tail == null){
                return result;
            }else {
                result = (V)head.value;
                if(head.next == null){
                    tail = null;
                }
                head = head.next;
                size--;
            }
            return result;
        }

        public int size(){
            return size;
        }


    }

TIPS：

队列的特性是：先进先出，所以先入队的元素，在出队时需要送头部弹出；
但是要求入队与出队的时间复杂度都是O(1)，所以需要head，tail 两个节点，分别记录头指针与尾指针。

题目4

你可以使用链表实现栈结构吗？入栈与入栈都是O(1)的时间复杂度。

public class Node<V> {
    V value; 
    Node<V> next;

    public Node(V value){
       this.value =value;
    }
}

参考题解：

public static class Stack<V> {

        Node<V> head;
        int size;

        public Stack(){
            size = 0 ;
            head = null ;
        }

        public void add(V data){
            Node node = new Node(data);
            if(head == null){
                head = node;
            }else{
                node.next = head;
                head = node;
            }
            size++;
        }

        public V pop(){
            V result = null;
            if(head != null){
                result = head.value;
                head = head.next;
                size --;
            }
            return result;
        }

        public int size(){
            return size;
        }


}

TIPS

本题解的栈指引入了一个成员变量，关键点在于：每次入栈以后，把当前节点的next指针执行之前的head节点；然后再把head指针执行当前节点。

题目5

你可以使用链表实现双端队列结构吗？

public class Node<V> {
    V value; 
    Node<V> next;
    Node<V> pre;

    public Node(V value){
       this.value =value;

    }
}

参考题解：

public static class Dqueue<V> {

        Node<V> head;
        Node<V> tail;
        int size;

        public Dqueue(){
            size = 0 ;
            head = null ;
            tail = null ;
        }

        public void lAdd(V data){
            Node node = new Node(data);
            if(head == null || tail == null){
               head = node;
               tail = node;
            }else{
               tail.next = node;
               tail = tail.next;
            }
            size++;
        }


        public void rAdd(V data){
            Node node = new Node(data);
            if(head == null || tail == null){
               head = node;
               tail = node;
            }else{
               head.pre = node;
               head = head.pre;
            }
            size++;
        }

        public V rPop(){
            V result = null;
            if(head!= null){
               result = (V) head.value;
               if(head.next == null){
                   tail = null;
               }
               head = head.next;
               size--;
            }
            return result;
        }

        public V lPop(){
            V result = null;
            if(tail!= null){
               result = (V) tail.value;
               if(tail.pre == null){
                   head = null;
               }
               tail = tail.pre;
               size--;
            }
            return result;
        }

        public int size(){
            return size;
        }


    }

TIPS

双端队列的话，
左进左出 或者 右进右出 可以形成栈结构
左进右出 或者 右进做出 可以进行队列结构