链表

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

考察点：链表
参考回答：
单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。
// 链表的节点结构如下 typedef struct node { int data; struct node *next; } NODE;
最常用方法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。
通过使用STL库中的map表进行映射。首先定义 map<NODE *, int> m; 将一个 NODE * 指针映射成数组的下标，并赋值为一个 int 类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，表示该节点第一次访问；而如果m[p]的值为1，则说明这个节点已经被访问过一次了，于是就形成了环。

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

考察点：链表
参考回答：

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

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

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

考察点：链表
参考回答：

public class
OddIncreaseEvenDecrease {
    /**
     * 按照奇偶位拆分成两个链表
     * @param head
     * @return
     */
    public static Node[] getLists(Node head){
        Node head1 = null;
        Node head2 = null;
        
        Node cur1 = null;
        Node cur2 = null;
        int count = 1;//用来计数
        while(head != null){
            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;
}

• 如何反转单链表

考察点：链表
参考回答：

ListNode
reverseList(ListNode* head) {
        if(head == nullptr || head->next ==
nullptr)
            return head;
        ListNode* p;
        ListNode* q;
        ListNode* r;
        p = head;
        q = head->next;
        head->next = nullptr;//旧的头指针是新的尾指针 指向NULL
        while(q){
            r = q->next;//用来保存下一步要处理的指针
            q->next = p;//p q 交替处理 进行反转单链表
            p = q;
            q = r;
        }
        head = p;//最后的q必定指向NULL，p就成了新链表的头指针
        return head;
}