链表 - 召田最帅boy

现在有一个单向链表，谈一谈，如何判断链表中是否出现了环

考察点：链表

参考回答：

单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。

解法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。

谈一谈，bucket如果用链表存储，它的缺点是什么？

考察点：链表

参考回答：

①查找速度慢，因为查找时，需要循环链表访问

②如果进行频繁插入和删除操作，会导致速度很慢。

有一个链表，奇数位升序偶数位降序，如何将链表变成升序

考察点：链表

思路：将链表按照奇偶数位分成两个链表head1和head2，如1->6->3->4->5->2，得到1->3->5和6->4->2两个链表，将6->4->2反转得到2->4->6，在将两个链表合并。

public class
OddIncreaseEvenDecrease {
    /**
     * 按照奇偶位拆分成两个链表
     * @param head
     * @return
     */
    // 例子 1 6 3 4 5 2 变成 1 2 3 4 5 6
    public static Node[] getLists(Node head){
        Node head1 = null;
        Node head2 = null;

        Node cur1 = null;
        Node cur2 = null;
        int count = 1;//用来计数
        while(head != null){
            // 遇到1 3 5 
            if(count % 2 == 1){
                if(cur1 != null){
                    cur1.next = head;
                    cur1 = cur1.next;
                }else{
                    cur1 = head;
                    head1 = cur1;
                }
            }else{
                if(cur2 != null){
                    cur2.next = head;
                    cur2 = cur2.next;
                }else{
                    cur2 = head;
                    head2 = cur2;
                }
            }
            head = head.next;
            count++;
        }
        //跳出循环，要让最后两个末尾元素的下一个都指向null
        cur1.next = null;
        cur2.next = null;

        Node[] nodes = new Node[]{head1,head2};
        return nodes;
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public static Node reverseList(Node head){
        Node pre = null;
        Node next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 合并两个有序链表
     * @param head1
     * @param head2
     * @return
     */
    public static Node CombineList(Node head1,Node head2){
        if(head1 == null || head2 == null){
            return head1 != null ? head1 :head2;
        }
        Node head = head1.value < head2.value ?head1 : head2;
        Node cur1 = head == head1 ? head1 :head2;
        Node cur2 = head == head1 ? head2 :head1;
        Node pre = null;
        Node next = null;
        while(cur1 != null && cur2 !=null){
            if(cur1.value <= cur2.value){//这里一定要有=，否则一旦cur1的value和cur2的value相等的话，下面的pre.next会出现空指针异常
                pre = cur1;
                cur1 = cur1.next;
            }else{
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;

        return head;
    }

}

随机链表的复制

考察点：链表

public RandomListNode copyRandomList(RandomListNode head) {

    if (head == null)
        return null;

    RandomListNode p = head;

    // copy every node and insert to list
    while (p != null) {
        RandomListNode copy = new RandomListNode(p.label);
        copy.next = p.next;
        p.next = copy;
        p = copy.next;
    }

    // copy random pointer for each new node
    p = head;
    while (p != null) {
        if (p.random != null)
            p.next.random = p.random.next;
        p = p.next.next;
    }

    // break list to two
    p = head;
    RandomListNode newHead = head.next;
    while (p != null) {
        RandomListNode temp = p.next;
        p.next = temp.next;
        if (temp.next != null)
            temp.next = temp.next.next;
        p = p.next;
    }

    return newHead;
}

如何反转单链表

考察点：链表

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