带头节点的单链表面试题汇总

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import org.apache.commons.io.IOUtils;

//带头节点的单链表
public class LinkedList2<T>
{
    public static void main(String[] args) throws CloneNotSupportedException
    {
        LinkedList2<Integer> list = new LinkedList2<Integer>(1, 2, 3, 4, 5);
        // System.out.println(list.isEmpty());
        // System.out.println(list.size());
        // System.out.println(list.createEntry(1).next);
        // System.out.println(list.getEntry(-1));
        // System.out.println(list.getEntry(0));
        // System.out.println(list.getEntry(2));
        System.out.println(list);

        // LinkedList2<Integer> n_list = (LinkedList2<Integer>) list.clone();
        // System.out.println(n_list);
        // LinkedList2.reverseListByIterator(n_list);
        // LinkedList2.reverseListByRecursion(n_list);
        // System.out.println(n_list);

        // Entry<Integer> entry = LinkedList2.lastIndexOf(list, 2);
        // Entry<Integer> entry = LinkedList2.lastIndexOfByArray(list, 5);
        // Entry<Integer> entry = LinkedList2.getMiddleEntry(list);
        // System.out.println(entry == null ? "not found" : entry.element);

        // LinkedList2.reversePrintListByStack(list);
        // LinkedList2.reversePrintListByRecursion(list);

        // LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 2, 2, 5);
        // LinkedList2<Integer> list2 = new LinkedList2<Integer>(2, 3, 3, 3, 4);
        // System.out.println(list1);
        // System.out.println(list2);
        // LinkedList2<Integer> n_list = LinkedList2.mergeList(list1, list2);
        // System.out.println(n_list);

        // LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3);
        // Entry<Integer> lastEntry = list1.getEntry(list1.size() - 1);
        // Entry<Integer> firstEntry = list1.getEntry(0);
        // lastEntry.next = firstEntry;
        // System.out.println(LinkedList2.hasLoop(list1));
        // Entry<Integer> entry = LinkedList2.getFirstEnterLoopEntry(list1);
        // Entry<Integer> entry = LinkedList2.getFirstEnterLoopEntry2(list1);
        // System.out.println(entry == null ? "no loop" : entry.element);

        // LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3, 4);
        // LinkedList2<Integer> list2 = new LinkedList2<Integer>(11, 22, 33,
        // 44);
        // // list2.getEntry(2).setNext(list1.getEntry(1));
        // list2.getEntry(3).setNext(list1.getEntry(3));
        // System.out.println(list1);
        // System.out.println(list2);
        // System.out.println(LinkedList2.isIntersect(list1, list2));
        // System.out.println(LinkedList2.isIntersect2(list1, list2));
        // System.out.println(LinkedList2.isIntersect3(list1, list2));
        //
        // Entry<Integer> entry = LinkedList2.getFirstIntersectEntry(list1,
        // list2);
        // System.out.println(entry == null ? "not found" : entry.element);

        // LinkedList2.deleteEntry(list, list.getEntry(4));
        // System.out.println(list);
	
        LinkedList2<Integer> list1 = new LinkedList2<Integer>(1, 2, 3, 4, 2, 3, 4, 5, 1);
        System.out.println(list1);
        LinkedList2.deleteDuplicateEntries(list1);
        System.out.println(list1);
    }

    //头指针
    private Entry<T> head;

    public LinkedList2()
    {
        //初始化一个头节点，让头指针指向这个头节点	
        head = new Entry<T>(null);
    }

    public LinkedList2(T... elements)
    {
        this();
        //尾指针,一开始指向头节点
        Entry<T> tail = head;
        for (T element : elements)
        {
            //实例化一个新的节点,next为null	    
            Entry<T> newEntry = new Entry<T>(element, null);
            //让尾指针的next指向新的节点
            tail.next = newEntry;
            //尾指针后移一位指向新的节点
            tail = newEntry;
        }
    }

    public void setHead(Entry<T> head)
    {
        this.head = head;
    }

    public boolean isEmpty()
    {
        //头节点的next为空，则整个链表为空
        return head.next == null;
    }

    // 1. 求单链表中结点的个数
    public int size()
    {
        if (isEmpty())
            return 0;

        Entry<T> curEntry = head.next;
        int c = 0;
        while (curEntry != null)
        {
            c++;
            curEntry = curEntry.next;
        }
        return c;
    }

    // 2. 将单链表反转: reverseList（遍历）
    public static <T> void reverseListByIterator(LinkedList2<T> list)
    {
        Entry<T> curEntry = list.head.next; //第一个节点
        Entry<T> nextEntry = null; //第二个节点
        Entry<T> nextnextEntry = null; //第三个节点

        //如果当前链表没有节点或者只有一个节点，直接返回
        if (curEntry == null || curEntry.next == null)
            return;

       //循环前:
       //             head -> first -> second -> third .. -> null
       //                     [cur]    [next]    [nextnext]   
       //一轮循环结束：
       //             head -> second -> first -> third .. -> null
       //                     [next]    [cur]    [nextnext]
       // ................
       //如果当前节点是最后一个节点，退出循环
        while (curEntry.next != null)
        {
            //当前节点的下一个节点
            nextEntry = curEntry.next;
            //当前节点的下下个节点
            nextnextEntry = nextEntry.next;
            //让第二个节点的next指向第一个节点
            nextEntry.next = list.head.next;
            //让头节点的next指向第二个节点
            list.head.next = nextEntry;
            //让第一个节点的next指向第三个节点
            curEntry.next = nextnextEntry;
        }
    }

    // 2. 将单链表反转: reverseListRec（递归）
    public static <T> void reverseListByRecursion(LinkedList2<T> list)
    {
        //同上，链表中没有节点或者只有一个节点，直接返回
        if (list.head.next == null || list.head.next.next == null)
            return;
        list.head.next = reverseList(list.head.next);
    }
    
    private static <T> Entry<T> reverseList(Entry<T> head)
    {
	    //比如有链表 1 -> 2 -> 3 -> 4 -> null
        //最后一轮的head是4 -> null,直接返回这个head
	    //倒数第二轮,head是3 -> 4 - > null,将最后一轮返回的head赋给newHead
        //newHead -> 4 -> null                    ↓ - - ↑
        //执行head.next.next = head 得到newHead -> 4 - > 3 出现了环
        //最后执行head.next = null将环打破, 得到newHead -> 4 - > 3 -> null
        //.........
	
        //如果是最后一个节点，直接返回
        if (head.next == null)
            return head;

        //倒数第二轮递归时，得到最后一轮返回的节点（最后一个节点），作为新链表的第一个节点
        Entry<T> newHead = reverseList(head.next);
        //第二个节点的next指向第一个节点
        head.next.next = head;
	    //第一个节点的next置为null
        head.next = null;
        return newHead;
    }


    // 3. 查找单链表中的倒数第K个结点（k > 0）
    public static <T> Entry<T> lastIndexOf(LinkedList2<T> list, int n)
    {
        if (n <= 0)
            throw new IllegalArgumentException("The number should be greater than zero");

        //获得第n个节点，赋值给first
        Entry<T> first = list.getEntry(n - 1);
        //second指向头节点
        Entry<T> second = list.head;
        //first和second以相同的频率前进,直到最后一个节点
        while (first != null)
        {
            first = first.next;
            second = second.next;
        }
        //此时second指针指向的节点就是倒数第n个节点
        return second;
    }

    // 3. 查找单链表中的倒数第K个结点（k > 0）,数组实现
    @SuppressWarnings("unchecked")
    public static <T> Entry<T> lastIndexOfByArray(LinkedList2<T> list, int n)
    {
        if (n <= 0)
            throw new IllegalArgumentException("The number should be greater than zero");

        Object[] entries = new Object[n];
        int c = 0, index = 0;
        Entry<T> curEntry = list.head.next;

        while (curEntry != null)
        {
            entries[index] = curEntry;
            index = (index + 1) % n; //索引值永远不会超过n
            c++;
            curEntry = curEntry.next;
        }

        if (entries[index] == null)
            throw new IllegalStateException("Less than " + n + " elements, current is " + c);
        return Entry.class.cast(entries[index]);
    }

    // 4. 查找单链表的中间结点
    public static <T> Entry<T> getMiddleEntry(LinkedList2<T> list)
    {
        if (list.isEmpty())
            return null;

        Entry<T> first = list.head;
        Entry<T> second = list.head;

        //first每次向前走两步，second每次走一步，当first到链表结尾，second指针指向的节点就是中间节点
        while (first != null && first.next != null)
        {
            first = first.next.next;
            second = second.next;
        }
        return second;
    }

    // 5. 从尾到头打印单链表,通过栈实现
    public static <T> void reversePrintListByStack(LinkedList2<T> list)
    {
        java.util.LinkedList<T> stack = new java.util.LinkedList<T>();
        Entry<T> curEntry = list.head;

        while (curEntry.next != null)
        {
            stack.push(curEntry.next.element);
            curEntry = curEntry.next;
        }

        String result = "[";
        while (!stack.isEmpty())
        {
            result += stack.pop();
            result += ", ";
        }
        if (result.length() > 1)
            result = result.substring(0, result.length() - 2);
        result += "]";
        System.out.println(result);
    }

    // 5. 从尾到头打印单链表（递归）
    public static <T> void reversePrintListByRecursion(LinkedList2<T> list)
    {
        String result = reversePrint(list.head);
        if (result.length() > 0)
            result = result.substring(0, result.length() - 2);

        System.out.println("[" + result + "]");
    }

    private static <T> String reversePrint(Entry<T> entry)
    {
        if (entry.next == null)
            return "";

        String result = reversePrint(entry.next);
        result += entry.next.element + ", ";
        return result;
    }

    // 6. 已知两个单链表list1和list2各自有序，把它们合并成一个链表依然有序
    @SuppressWarnings("unchecked")
    public static <T> LinkedList2<T> mergeList(LinkedList2<T> list1, LinkedList2<T> list2)
    {
        Entry<T> curEntry1 = list1.head;
        Entry<T> curEntry2 = list2.head;
        Entry<T> newHead = new Entry<T>(null);
        Entry<T> preEntry = newHead;

        while (curEntry1.next != null && curEntry2.next != null)
        {
            //如果entry1的element小于entry2的element，则把entry1加到新的链表中去
            if (((Comparable) curEntry1.next.element).compareTo(curEntry2.next.element) < 0)
            {
                //每次重新实例化一个节点对象
                preEntry.next = new Entry<T>(curEntry1.next.element, null);
                curEntry1 = curEntry1.next;
            }
            else
            {
                //否则，把entry2加到新链表中去
                preEntry.next = new Entry<T>(curEntry2.next.element, null);
                curEntry2 = curEntry2.next;
            }
            preEntry = preEntry.next;
        }

        //将list1链表剩余的entry加到新的链表中去
        while (curEntry1.next != null)
        {
            preEntry.next = new Entry<T>(curEntry1.next.element);
            curEntry1 = curEntry1.next;
            preEntry = preEntry.next;
        }

	   //将list2链表剩余的entry加到新的链表中去
        while (curEntry2.next != null)
        {
            preEntry.next = new Entry<T>(curEntry2.next.element);
            curEntry2 = curEntry2.next;
            preEntry = preEntry.next;
        }

        //返回一个全新的链表
        LinkedList2<T> result = new LinkedList2<T>();
        result.setHead(newHead);
        return result;
    }

    // 7. 判断一个单链表中是否有环
    public static <T> boolean hasLoop(LinkedList2<T> list)
    {
        Entry<T> first = list.head;
        Entry<T> second = list.head;
       
        //first每次往前走两步，second每次走一步，当在某个节点first和second相等了，说明这个链表存在环
        while (first != null && first.next != null)
        {
            first = first.next.next;
            second = second.next;

            if (first == second)
                return true;
        }
        return false;
    }

    // 8. 已知一个单链表中存在环，求进入环中的第一个节点
    public static <T> Entry<T> getFirstEnterLoopEntry(LinkedList2<T> list)
    {
        Entry<T> first = list.head;
        Entry<T> second = list.head;

        //first每次往前走两步，second每次走一步，当在某个节点first和second相等了，说明有环，
        //此时，让first从这个相交的节点开始，second从头节点开始，每次往前走一步，
        //当first和second再次相同, 这个节点就是进入环的第一个节点
        while (first != null && first.next != null)
        {
            first = first.next.next;
            second = second.next;

            if (first == second)
                break;
        }

        if (first == null || first.next == null)
            return null;

        second = list.head;
        while (first != second)
        {
            first = first.next;
            second = second.next;
        }
        return first;
    }

    // 8. 已知一个单链表中存在环，求进入环中的第一个节点 HashMap实现
    public static <T> Entry<T> getFirstEnterLoopEntry2(LinkedList2<T> list)
    {
        HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();
        Entry<T> curEntry = list.head;

        //每次将节点放到map之前，检查一下map中是否已经存在这个节点了，如果存在，那这个节点就是
        //进入环中的第一个节点了
        while (curEntry != null)
        {
            if (storage.get(curEntry) == Boolean.TRUE)
                return curEntry;
            else
            {
                storage.put(curEntry, Boolean.TRUE);
                curEntry = curEntry.next;
            }
        }
        return null;
    }

    // 9. 判断两个单链表是否相交 HashMap实现
    public static <T> boolean isIntersect(LinkedList2<T> list1, LinkedList2<T> list2)
    {
        Entry<T> curEntry1 = list1.head;
        Entry<T> curEntry2 = list2.head;
        HashMap<Entry<T>, Boolean> storage = new HashMap<Entry<T>, Boolean>();

        //将list1中的节点都存储到map中去
        while (curEntry1.next != null)
        {
            storage.put(curEntry1.next, Boolean.TRUE);
            curEntry1 = curEntry1.next;
        }

        //遍历list2中的节点，跟map中已存在的节点比较，如果找到相同的节点，
        //这个节点就是两个链表的交点
        while (curEntry2.next != null)
        {
            if (storage.get(curEntry2.next) == Boolean.TRUE)
                return true;
            curEntry2 = curEntry2.next;
        }
        return false;
    }

    // 9. 判断两个单链表是否相交 如果相交 让第一个链表的next指向第二个链表的头指针，可以构成一个环
    public static <T> boolean isIntersect2(LinkedList2<T> list1, LinkedList2<T> list2)
    {
        Entry<T> curEntry1 = list1.head;
        Entry<T> curEntry2 = list2.head;

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

        curEntry1.next = list2.head;
        boolean exist = false;
        while (curEntry2.next != null)
        {
            if (curEntry2.next == list2.head)
            {
                exist = true;
                break;
            }
            curEntry2 = curEntry2.next;
        }
        //将list1的next置为null，一定不要忘记
        curEntry1.next = null;
        return exist;
    }

    // 9. 判断两个单链表是否相交 如果相交 最后一个节点一定相等
    public static <T> boolean isIntersect3(LinkedList2<T> list1, LinkedList2<T> list2)
    {
        Entry<T> curEntry1 = list1.head;
        Entry<T> curEntry2 = list2.head;

        while (curEntry1.next != null)
            curEntry1 = curEntry1.next;
        
        while (curEntry2.next != null)
            curEntry2 = curEntry2.next;

        if (curEntry1 == curEntry2)
            return true;
        return false;
    }

    // 10. 求两个单链表相交的第一个节点
    public static <T> Entry<T> getFirstIntersectEntry(LinkedList2<T> list1, LinkedList2<T> list2)
    {
        Entry<T> curEntry1 = list1.head;
        Entry<T> curEntry2 = list2.head;
        int m = 0, n = 0;

        //得到第一个链表的长度
        //m = list1.size();
        while (curEntry1.next != null)
        {
            m++;
            curEntry1 = curEntry1.next;
        }

        //得到第二个链表的长度
        //n = list2.size()
        while (curEntry2.next != null)
        {
            n++;
            curEntry2 = curEntry2.next;
        }

        curEntry1 = list1.head;
        curEntry2 = list2.head;
        int c;
        if (m > n)
        {
            c = m - n;
            while (c != 0)
            {
                curEntry1 = curEntry1.next;
                c--;
            }
        }
        else
        {
            c = n - m;
            while (c != 0)
            {
                curEntry2 = curEntry2.next;
                c--;
            }
        }

	    //让list1和list2从同一个起点开始遍历
        while (curEntry1 != null)
        {
            curEntry1 = curEntry1.next;
            curEntry2 = curEntry2.next;

            //这个相同的entry就是交点
            if (curEntry1 == curEntry2)
                return curEntry1;
        }
        return null;
    }

    // 11. 给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted: delete
    public static <T> void deleteEntry(LinkedList2<T> list, Entry<T> entry)
    {
        if (entry == null)
            return;

        //当前节点不是最后一个节点
        if (entry.next != null)
        {
            entry.element = entry.next.element;
            entry.next = entry.next.next;
        }
        else
        {
            //最后一个节点，且该链表仅有一个元素
            if (list.head.next == entry)
                list.head.next = null;
            else
            {
                //链表包含多个元素
                Entry<T> preEntry = list.head;
                while (preEntry.next != null && preEntry.next != entry)
                {
                    preEntry = preEntry.next;
                }
                if (preEntry.next == null)
                    throw new IllegalStateException("No element found " + entry);
                preEntry.next = preEntry.next.next;
            }
        }
    }

    // 12.删除单链表中重复的元素
    public static <T> void deleteDuplicateEntries(LinkedList2<T> list)
    {
        Set<T> entries = new HashSet<T>();
        Entry<T> curEntry = list.head;

        while (curEntry.next != null)
        {
            if (entries.contains(curEntry.next.element))
                curEntry.next = curEntry.next.next;
            else
            {
                entries.add(curEntry.next.element);
                curEntry = curEntry.next;
            }
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public Object clone() throws CloneNotSupportedException
    {
        try
        {
            ByteArrayOutputStream baos = new ByteArrayOutputStream();
            ObjectOutputStream oos = new ObjectOutputStream(baos);
            try
            {
                oos.writeObject(head);
                oos.flush();

                ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray()));
                try
                {
                    LinkedList2<T> result = new LinkedList2<T>();
                    result.setHead(Entry.class.cast(ois.readObject()));
                    return result;
                }
                finally
                {
                    IOUtils.closeQuietly(ois);
                }
            }
            finally
            {
                IOUtils.closeQuietly(oos);
            }
        }
        catch (Exception e)
        {
            e.printStackTrace();
            return super.clone();
        }
    }

    public Entry<T> createEntry(T element)
    {
        return new Entry<T>(element);
    }

    public Entry<T> getEntry(int index)
    {
        if (index < 0)
            throw new IllegalArgumentException("index should be a positive number or zero");
        int c = 0;
        Entry<T> curEntry = head.next;
        while (curEntry != null && c < index)
        {
            curEntry = curEntry.next;
            c++;
        }

        if (curEntry == null)
            throw new IllegalStateException("Less than " + (index + 1) + " elements, current is " + c);

        return curEntry;
    }

    @Override
    public String toString()
    {
        String result = "[";
        Entry<T> curEntry = head.next;
        while (curEntry != null)
        {
            result += curEntry.element;
            curEntry = curEntry.next;
            if (curEntry != null)
                result += ", ";
        }
        return result + "]";
    }

    public static class Entry<T> implements Serializable
    {
        private static final long serialVersionUID = 1L;
        T element;
        Entry<T> next;

        public void setElement(T element)
        {
            this.element = element;
        }
	
        public T getElement()
        {
            return element;
        }

        public void setNext(Entry<T> next)
        {
            this.next = next;
        }

        Entry(T element)
        {
            this(element, null);
        }

        Entry(T element, Entry<T> next)
        {
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString()
        {
            return String.valueOf(element);
        }
    }
}