算法：链表

一、引言 §

链表是一种非线性数据结构，各种语言中给链表分配内存时不是一块整体的，可以充分利用碎片内存。相对线性的数据结构，链表对增加和删除节点比较高效，对读节点效率低一些。另外非线性结构需要保存下一个节点的指针，内存占用会大一些。

二、 高频面试题 §

• 反转链表

 
/**  
 * 非递归方式反转链表head 到 end，不包括 end  
 * @param head  
 * @param end: 不包括  
 * @return  
 */  
public static ListNode reverse1(ListNode head, ListNode end) {  
    if(head == end || head.getNext() == end) return head;  
  
    ListNode pre = null;  
    ListNode cur = head;  
    while(cur != end) {  
        ListNode next = cur.getNext();  
        cur.setNext(pre);  
        pre = cur;  
        cur = next;  
    }  
  
    return pre;  
}
 
/**  
 * 递归方式反转链表  
 * @param head  
 * @return  
 */  
public static ListNode reverse2(ListNode head) {  
    if(head == null || head.getNext() == null) return head;  
  
    ListNode next = head.getNext();  
    ListNode newHead = reverse2(next);  
    next.setNext(head);  
    head.setNext(null);  
  
    return newHead;  
}
 

• K 个一组反转链表

/**  
 * k个一组反转链表，不足 k 个时不反转  
 * @param head  
 * @param k  
 * @return  
 */  
public static ListNode reverseKGroup(ListNode head, int k) {  
    // 加入 dummy 好计算 K 个节点  
    ListNode dummy = new ListNode(-1);  
    dummy.setNext(head);  
    ListNode p = dummy;  
    for(int i = 0; i < k; i++) {  
        if(p == null || p.getNext() == null) return head;  
        p = p.getNext();  
    }  
  
    // 第 2 组的首个节点  
    ListNode next = p.getNext();  
    // g1Head为第 1 组反转后的头节点  
    ListNode g1Head = reverse1(head, next);  
  
    // 从第 2 组开始继续递归，g2Head为第 2 组反转后的头节点  
    ListNode g2Head = reverseKGroup(next, k);  
    // head 现在为第 1 组的尾节点了  
    head.setNext(g2Head);  
  
    return g1Head;  
}

• 求链表中间节点

/**  
 * 找链表的中间节点。奇数节点返回中间节点；偶数节点返回 2 个中间节点中的第 2 个节点，本场景主要方便回文比较  
 * 1, 2, 3 返回 2  
 * 1，2，3，4 返回 3  
 * @param head  
 * @return  
 */  
public static ListNode findTheMid(ListNode head) {  
    if(head == null) return head;  
  
    ListNode slow = head, fast = head;  
    while(fast != null && fast.getNext() != null) {  
        slow = slow.getNext();  
        fast = fast.getNext().getNext();  
    }  
  
    return slow;  
}

• 判断链表是否有环

/**  
 * 通过快慢指针判断链表是否有环  
 * @param head  
 * @return  
 */  
private static boolean hasCycle(ListNode head) {  
    if(head == null || head.getNext() == null) return false;  
  
    ListNode slow = head, fast = head.getNext().getNext();  
  
    while(fast != null && fast.getNext() != null) {  
        if(slow == fast) return true;  
        slow = slow.getNext();  
        fast = fast.getNext().getNext();  
    }  
  
    return false;  
}	

• 判断链表是否是回文

/**  
 * 判断以 head 开头的链表节点是否构成回文  
 * @param head  
 * @return  
 */  
public static boolean isPalindrome(ListNode head) {  
    // 找到中间节点。奇数节点返回中间节点；偶数节点返回 2 个中间节点中的第 2 个节点  
    ListNode mid = findTheMid(head);  
    // 反转中间节点和尾节点间的元素  
    ListNode newHead = reverseToTheEnd(mid);  
    // 顺序比较前后 2 组节点是否一样  
    while(head != null && newHead != null) {  
        if(head.getVal() != newHead.getVal()) return false;  
  
        head = head.getNext();  
        newHead = newHead.getNext();  
    }  
  
    return true;  
}

• 求 2 个链表的相交节点

/**  
 * 求 2 个链表的相交节点。如果不存在的话返回 null  
 * @param head1  
 * @param head2  
 * @return  
 */  
public static ListNode isIntersect(ListNode head1, ListNode head2) {  
    ListNode p1 = head1;  
    ListNode p2 = head2;  
  
    while(p1 != null && p2 != null) {  
        if(p1 == p2) return p1;  
  
        p1 = p1.getNext();  
        if(p1 == null) p1 = head2;  
  
        p2 = p2.getNext();  
        if(p2 == null) p2 = head1;  
    }  
  
    return null;  
}

三、总结 §

1. 为了把对头节点和其他节点的处理统一，一般会加入dummy 节点。这样边界逻辑处理会少一些；
2. 链表算法中关键点是前后节点指针的处理，需要避免构成循环；
3. 多练、多推演。