链表相关算法

一. 简介

根据维基百科的定义:链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

二. 实际应用

根据链表结构插入和删除效率特别高的特点,链表主要用于插入和删除数据比较频繁并要求高效率的场景,比如:

  1. 操作系统的文件系统管理和内存池等。
  2. 内存数据库Redis中就有多个功能(发布与订阅、慢查询、监视器等)用到了无环双向链表。
  3. 版本管理系统Git的很多操作也是基于链表。merge和rebase等操作就是直接将链表指针移动到对应的branch所对应的node。
  4. 还有一些场景中,如果对使用线性表的长度和规模无法预测和控制时,会改为使用链表,比如通讯录等。

三. 常见算法

本文中所有的单向链表和双向链表的结构定义如下:

//单向链表    
public class Node {
    private int value;
    private Node next;
...
}

//双向链表
public class DoublyNode {
    private int value;
    private DoublyNode previous;
    private DoublyNode next;
    ...
}

1. 在O(1)时间删除链表节点

题目描述: 给定链表的头指针和一个节点指针,在O(1)时间删除该节点。

分析: 本题主要思想是用下一个节点数据覆盖要删除的节点,然后删除下一个节点。如果待删除节点是尾节点时,直接删除该节点即可, 但是需要注意的是,这种情况下时间复杂度是O(N)而不是O(1)。

代码如下:

/**
 * Given a linked list, delete the node in O(1) time complexity.
 * @param headNodeBeforeDeletingNode The source head node of the linked list
 * @param nodeToBeDeleted The node need to be deleted.
 * @return The head node of the linked list after deleting the node.
 */
public Node deleteNodeInO1TimeComplexity(Node headNodeBeforeDeletingNode, Node nodeToBeDeleted) {
    if(null == headNodeBeforeDeletingNode || null == nodeToBeDeleted){
        System.out.println("The source linked list or the node to be deleted is null, will do nothing!");
        return headNodeBeforeDeletingNode;
    }

    if(null == nodeToBeDeleted.getNext()){
        //Note: Here if the node need to be removed is the last node of the list, we will
        //not be able to delete it in O(1) time complexity, it's gonna to be O(N).
        Node tempNode = headNodeBeforeDeletingNode;
        while(tempNode.getNext() != null){
            if(tempNode.getNext().equals(nodeToBeDeleted)){
                tempNode.setNext(null);
                return headNodeBeforeDeletingNode;
            }
            tempNode = tempNode.getNext();
        }
    }else{
        Node nextNode = nodeToBeDeleted.getNext();
        nodeToBeDeleted.setValue(nextNode.getValue());
        nodeToBeDeleted.setNext(nextNode.getNext());
    }
    return headNodeBeforeDeletingNode;
}

2. 单链表的转置(transpose)

题目描述: 输入一个单向链表,输出逆序反转后的链表

分析: 用两个辅助指针 pre、next 在链表上循环一遍即可

代码如下:

/**
 * Transpose the linked list to a reverse order.
 * @param headNodeOfSourceList The head node of the source linked list
 * @return The head node of the transposed linked list.
 */
public Node transposeLinkedList(Node headNodeOfSourceList){
    if(null == headNodeOfSourceList || headNodeOfSourceList.getNext() == null){
        System.out.println("The source linked list is null or only has 1 element, will do nothing!");
        return headNodeOfSourceList;
    }
    Node pre = null;
    Node next = null;
    Node cur = headNodeOfSourceList;
    while(cur != null){
        next = cur.getNext();
        cur.setNext(pre);
        pre = cur;
        cur = next;
    }
    return pre;
}

3. 求链表倒数第k个节点

题目描述: 输入一个单向链表,输出该链表中倒数第k个节点,链表的倒数第0个节点为链表的尾指针。

分析: 设置两个指针 p1、p2,首先 p1 和 p2 都指向 head,然后 p2 向前走 k 步,这样 p1 和 p2 之间就间隔 k 个节点,最后 p1 和 p2 同时向前移动,直至 p2 走到链表末尾。

代码如下:

/**
 * Given a linked list and a int k(between 1 and length of list), get the last K node.
 * @param headNodeOfSourceList
 * @param k The int k(between 1 and length of list)
 * @return The last k node
 */
public Node getLastKNodeOfTheLinkedList(Node headNodeOfSourceList, int k){
    Node position1 = headNodeOfSourceList;
    Node position2 = headNodeOfSourceList;
    int j = k;
    //First, move position2 to the k-th element of the list.
    while(j > 1){
        position2 = position2.getNext();
        j--;
    }

    //Then move both position1 and position2 forward, when position2 reach end,
    // position1 is the last k-th element.
    while(position2.getNext() != null){
        position1 = position1.getNext();
        position2 = position2.getNext();
    }

    return position1;
}

4. 求链表的中间节点

题目描述: 求链表的中间节点,如果链表的长度为偶数,返回中间两个节点的任意一个,若为奇数,则返回中间节点。

分析: 此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度,然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表,如何解决呢?最高效的解法和第3题一样,通过两个指针来完成。用两个指针从链表头节点开始,一个指针每次向后移动两步,一个每次移动一步,直到快指针移到到尾节点,那么慢指针即是所求。

代码如下:

/**
 * Given a linked list, get the middle node of the list:
 * If the length is odd, return the middle; else return any of the middle 2 node.
 * @param headNodeOfSourceList
 * @return The middle node
 */
public Node getMiddleNodeOfTheLinkedList(Node headNodeOfSourceList){
    Node position1 = headNodeOfSourceList;
    Node position2 = headNodeOfSourceList;

    //Then move both position1 and position2 forward, when position2 reach end,
    // position1 is the last k-th element.
    while(position2 != null && position2.getNext() != null){
        position1 = position1.getNext();
        position2 = position2.getNext().getNext();
    }

    return position1;
}

5. 判断单链表是否存在环

题目描述: 输入一个单向链表,判断链表是否有环。

分析:

  1. 通过两个指针,分别从链表的头节点出发,一个每次向后移动一步,另一个移动两步,两个指针移动速度不一样,如果存在环,那么两个指针一定会在环里相遇。
  2. p作为指针从表头结点开始以1为步长遍历,边遍历边将表反向,如果p遇到NULL,则说明表没有环;如果p最后等于head,则说明表有环。
  3. 利用一个List和一个指针p,从头结点出发,依次判断每个节点的指针是否存在于List中,如果存在则表示有环,且p就是环的入口点,否则循环结束后p==null,没有环;

代码如下:

以下为使用方法1的代码:

/**
 * Given a linked list, check if it has circle:
 * @param headNodeOfSourceList
 * @return The flag of if it has circle
 */
public boolean checkIfLinkedListHasCircle(Node headNodeOfSourceList){
    Node position1 = headNodeOfSourceList;
    Node position2 = headNodeOfSourceList;

    //Then move both position1 and position2 forward, if position2 reach null means no circle,
    // else position2 will catch up with position1 when there is circle.
    while(position2 != null && position2.getNext() != null){
        position1 = position1.getNext();
        position2 = position2.getNext().getNext();
        if(position1.equals(position2)){
            return true;
        }
    }
    return false;
}

6. 找到环的入口点

题目描述: 输入一个单向链表,判断链表是否有环。如果链表存在环,如何找到环的入口点。

分析:

  1. 简单的方法: 类似于判断是否单链表中存在环,使用其中的方法3,利用一个List和一个指针p,从头结点出发,依次判断每个节点的指针是否存在于List中,如果存在则表示有环,且p就是环的入口点

  2. 双指针的方法

找到单链表环入口

h是链表起始点,s是环入口,p是两个指针碰撞点。r表示环的长度,r = x+y.
可以证明, a = y + mr (头指针 到 环入口的距离 = 碰撞点p 到 环入口的距离 + 循环多次环 )。证明如下:
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则: 2s = s + nr s= nr 设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。

s = nr
a + x = nr
a + x = (n – 1)r +r = (n-1)r + r 
a = (n-1)r + r - x
a = (n-1)r + y

由此可知,从链表头到环入口点等于(n-1)循环内环+ 相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。

代码如下:

以下为使用方法1的代码:

/**
 * Given a linked list, get the entry node of the circle if the linked list has circle.
 * Using 2 pointers
 * @param headNodeOfSourceList
 * @return The middle node
 */
public Node getCircleEntryNodeOfTheLinkedListWithCircle2(Node headNodeOfSourceList){
    Node position1 = headNodeOfSourceList;
    Node position2 = headNodeOfSourceList;

    //Then move both position1 and position2 forward, when position2 reach end,
    // position1 is the last k-th element.
    while(position2 != null && position2.getNext() != null){
        position1 = position1.getNext();
        position2 = position2.getNext().getNext();
    }

    return position1;
}

以下为使用方法2的代码:

/**
 * Given a linked list, get the entry node of the circle if the linked list has circle.
 * Using 2 pointers
 * @param headNodeOfSourceList
 * @return The middle node
 */
public Node getCircleEntryNodeOfTheLinkedListWithCircle2(Node headNodeOfSourceList){
    Node position1 = headNodeOfSourceList;
    Node position2 = headNodeOfSourceList;

    //Then move both position1 and position2 forward, when position2 reach end,
    // position1 is the last k-th element.
    while(position2 != null && position2.getNext() != null){
        position1 = position1.getNext();
        position2 = position2.getNext().getNext();
        if(position1.equals(position2)){
            //先判断是否有环
            break;
        }
    }

    //不存在环返回null
    if(!position1.equals(position2)){
        return null;
    }

    //快指针重新从表头开始按照步长1走,与慢指针相遇的点就是环入口。
    position2 = headNodeOfSourceList;
    while(!position1.equals(position2)){
        position1 = position1.getNext();
        position2 = position2.getNext();
    }

    return position1;
}

7. 编程判断两个链表是否相交

题目描述: 给出两个单向链表的头指针(如下图所示),
2 linked list
比如h1、h2,判断这两个链表是否相交。这里为了简化问题,我们假设两个链表均不带环。

分析:

解题思路:

“如果两个没有环的链表相交于某一节点,那么在这个节点之后的所有节点都是两个链表共有的”这个特点,我们可以知道,如果它们相交,则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点,所以这成了我们简化解法的一个主要突破口。那么,我们只要判断两个链表的尾指针是否相等。相等,则链表相交;否则,链表不相交。
所以,先遍历第一个链表,记住最后一个节点。然后遍历第二个链表,到最后一个节点时和第一个链表的最后一个节点做比较,如果相同,则相交,否则,不相交。这样我们就得到了一个时间复杂度,它为O((Length(h1) + Length(h2)),而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N),空间复杂度为O(1)

代码如下:

/**
     * Given 2 linked list, check if they intersect:
     * @param headNodeOfSourceList1 The head node of list 1
     * @param headNodeOfSourceList2 The head node of list 2
     * @return The flag of if the two linked list intersect
     */
    public boolean checkIfLinkedListHasCircle(Node headNodeOfSourceList1, Node headNodeOfSourceList2){
        if(headNodeOfSourceList1 == null || headNodeOfSourceList2 == null){
            return false;
        }
        while(headNodeOfSourceList1.getNext() != null){
            headNodeOfSourceList1 = headNodeOfSourceList1.getNext();
        }

        while(headNodeOfSourceList2.getNext() != null){
            headNodeOfSourceList2 = headNodeOfSourceList2.getNext();
        }

        return headNodeOfSourceList1.equals(headNodeOfSourceList2);
    }

8. 两链表相交的第一个公共节点

题目描述: 如果两个无环单链表相交,怎么求出他们相交的第一个节点呢?

分析: 采用对齐的思想。计算两个链表的长度 L1 , L2,分别用两个指针 p1 , p2 指向两个链表的头,然后将较长链表的 p1(假设为 p1)向后移动L2 - L1个节点,然后再同时向后移动p1 , p2,直到 p1 = p2。相遇的点就是相交的第一个节点。

代码如下:

/**
 * Get the lengh of the linked list
 * @param headNodeOfSourceList The head node of the linked list
 * @return The length of the linked list
 */
private int getLengthOfLinkedList(Node headNodeOfSourceList){
    if(null == headNodeOfSourceList){
        return 0;
    }
    int length = 0;
    while(headNodeOfSourceList != null){
        headNodeOfSourceList = headNodeOfSourceList.getNext();
        length++;
    }
    return  length;
}

/**
 * Given 2 linked list, get the first common node of the 2 intersected linked list.
 * @param headNodeOfSourceList1 The head node of list 1
 * @param headNodeOfSourceList2 The head node of list 2
 * @return The intersect node of 2 linked list
 */
public Node getIntersectNodeOfTheTwoIntersectLinkedList(Node headNodeOfSourceList1, Node headNodeOfSourceList2){
    int length1 = getLengthOfLinkedList(headNodeOfSourceList1);
    int length2 = getLengthOfLinkedList(headNodeOfSourceList2);

    //First move the longer linked list to the same size node postion as the other one
    if(length1 < length2){
        for(int i = 0; i < length2 - length1; i++)
        {
            headNodeOfSourceList2 = headNodeOfSourceList2.getNext();
        }
    }else{
        for(int i = 0; i < length1 - length2; i++)
        {
            headNodeOfSourceList1 = headNodeOfSourceList1.getNext();
        }
    }

    //Then move both linked list forward, the first equal node is the intesect node
    while(null != headNodeOfSourceList1 && !headNodeOfSourceList1.equals(headNodeOfSourceList2)){
        headNodeOfSourceList1 = headNodeOfSourceList1.getNext();
        headNodeOfSourceList2 = headNodeOfSourceList2.getNext();
    }

    return headNodeOfSourceList1;
}

四. 代码

本文中所有代码,可访问Github获取:LinkedListAlgorithms.java

五. 参考文献

  1. Jark’s Blog - 面试精选:链表问题集锦
  2. 链表- 维基百科
  3. 算法(十四)-单链表的环问题