单向链表中的一些算法

1. 在一个单向链表中，寻找链表中间节点。

使用两个指针，快指针每次步进为2，慢指针每次步进为1。当快指针到达链表尾部时，慢指针指向的就是链表的中间。

 

Node findMiddleNode(Node head) {
    if (head == null)
        return head;
    
    Node p1 = head;
    Node p2 = p1.next;
  
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
    }
    return p1;
}

 

2. 在单向链表中寻找倒数第n个元素

思路同1，使用两个指针，它们之间保持n的距离，当第一个指针到达链表尾部时，第二个指针指向的就是链表的倒数第n个元素。

 

Node findLastNNode(Node head, int n) {
    Node p1 = head;
    Node p2 = head;
    
    int i;
    for (i = 0; p1 != null && i < n; i++) {
        p1 = p1.next;
    } 
    if (i != n)
        return null;  // 链表长度小于n
  
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

 

3. 判定链表中是否存在环

思路同1，使用两个指针，p1每次步进为2，p2每次步进为1，循环直到p2等于null或者两个指针相等。若p2==null，说明该链表不存在环；若p1==p2，说明存在环。

 

bool isLoop(Node head) {
    if (head == null)
        return false;
    Node p1 = head;
    Node p2 = p1.next;

    while (p2 != null && p2.next != null && p1 != p2) {
        p1 = p1.next;
        p2 = p2.next.next;
    }
    if (p1 == p2) 
        return true;
    else
        return false;
}