单链表算法的java实现

发表于   |  

单链表的数据结构非常简单，但是基于单链表的一些算法却特别有意思。这里对各个算法的思路、要点、java实现、测试做一个简单的总结，具体如下：

  • 单链表的倒序输出
  • 查到单链表倒数第k个元素
  • 获取单链表的中间元素
  • 两个有序单链表合并
  • 判断两个单链表是否相交
  • 获取两个单链表相交的结点
  • 判断单链表是否有环
  • 判断有环单链表中，环的长度
  • 获取单链表中，环的起始结点
  • 删除单链表中指定结点

完整代码（包括测试用例）: (https://github.com/FergusChen/AlgoCode)
包路径：main.linklist

单链表的数据结构

首先，定义单链表的数据结构。

1
2
3
4
5
6
7
8
9
public class Node {
    public int data; //数据域
    public Node next; //指针域
    public Node(int data){
        this.data = data;
    }
}

单链表的倒序输出

单链表的倒序输出即从链表表尾逐个输出到表头。因为单链表的指针域是单向的，所以要找到表尾的话，需要遍历整个链表。
这个算法可以有两种实现：1、迭代实现，2、递归实现。

迭代实现

迭代实现关键是考虑倒序输出正好符合栈的先进后出的特点——先遍历到的元素最后输出。这样，可以遍历一遍，将数据存储在栈中，然后由栈逐个pop即可。下面是用迭代实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* -------单链表的倒序输出-------
* test (null), (d1)
* @param head 待倒序输出的链表
*
*/
public static void printListReversingly_Iterattively(Node head) {
    Stack<Integer> nodes = new Stack<Integer>();
        Node pNode = head;
    while (pNode != null) {
        nodes.push(pNode.data);
        pNode = pNode.next;
    }
    while (!nodes.isEmpty()) {
        System.out.print(nodes.pop() + ", ");
    }
}

递归实现

递归实现即递归地往下找，直到找到最后一个元素，再回溯输出即可。但是，递归实现有个很大的缺陷，就是当链表元素特别多的时候，递归层次太深，容易造成栈溢出。 。下面是递归实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
/**
* -------单向链表的倒序输出-------
* @param head 待倒序输出的链表
*/
public static void printListReversingly_Recursively(Node head) {
    if (head != null) {
        if (head.next != null) {
            printListReversingly_Recursively(head.next);
        }
        System.out.print(head.data + ", ");
    }
}

查找单链表倒数第k个元素

查找单链表中倒数第k个元素，仍然有两种实现：1、通过获取链表的长度实现。2、通过两个指针实现。

通过获取链表的长度的实现

第1次遍历，得到链表长度 length。然后第2次遍历，找到第length-k个元素就是了。这种方法效率较低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 查找单链表倒数第k个元素
 * test: (null, 2), (p1, 2), (p1, 200), (p1, 0)
 * @param head 待查找的链表
 * @param k 倒数第k个元素
 * @return Node 返回倒数第k个结点。若k=0或链表为null，则返回null，若k大于链表长度，则抛RuntimeException异常
 */
public static Node getReKthNode1(Node head, int k) {
    if (head == null || k == 0) return null;
    int length = 0;
    Node cur = head;
    while (cur != null) {
        cur = cur.next;
        ++length;
    }
    //这里做一步异常处理
    if (k > length) {
        throw new RuntimeException("exceed length of linklist");
    }
    cur = head;
    for (int i = 0; i < length - k; i++) {
        cur = cur.next;
    }
    return cur;
}

通过两个指针实现

如果不允许遍历整个链表，或者要提高效率，就采用这种思路：

  • 定义两个指针，pFront先指向第k个元素，pBack指向链表的head
  • 两个指针同时移动遍历，当pFront遍历到链表尾部之后，pBack正好是指向倒数第k个元素。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    /**
     * 查到单链表倒数第k个元素
     * test: (null, 2), (p1, 2), (p1, 200), (p1, 0)
     * @param head 待查找的结点
     * @param k 倒数第k个元素
     * @return Node 返回倒数第k个结点 ， 若k=0或链表为null，则返回null，若k大于链表长度，则抛RuntimeException异常
     */
    public static Node getReKthNode2(Node head, int k) {
        if (head == null || k == 0) return null;
        Node pFront = head; 
        Node pBack = head;
        while (k > 1 && pFront != null) { //从1开始数第k个数。
            pFront = pFront.next;
            --k;
        }
        if (pFront == null) {
            throw new RuntimeException("exceed length of linklist");
        }
        while (pFront.next != null) {
            pBack = pBack.next;
            pFront = pFront.next;
        }
        return pBack;
    }

获取单链表的中间元素

思路：仍然是两个指针，只是pFront一次走2步，pBack一次走1步。直到pFront走到最后一个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 获取单链表的中间元素。
 * test： （null）, (奇数个)， （偶数个）， （1个元素）
 * @param head 待查找的链表
 * @return Node 链表的中间结点。 若链表为null，则返回null
 */
public static Node getMiddleNode(Node head) {
    if (head == null || head.next == null) return head;
    Node pFront = head;
    Node pBack = head;
    while (!(pFront.next == null || pFront.next.next == null)) {
        pFront = pFront.next.next;
        pBack = pBack.next;
    }
    return pBack;
}

两个有序单链表合并

两个单链表head1和head2都各自有序，要求将其合并，得到的结果依然有序。。此问题仍然有两种实现：1、归并排序的思想合并； 2、递归合并

归并排序的思想合并

思想：用归并排序merge方法的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 两个有序单链表合并
 * test： (null, null), (null, head2), (head1, null), (head1,head2) 
 * @param head1 第1个有序链表
 * @param head2 第2个有序链表
 * @return Node 归并之后的结果链表 若两个链表都为null，则返回null
 */
public static Node mergeSortedLinklist1(Node head1, Node head2) {
    if (head1 == null) {
        return head2;
    }
    if (head2 == null) {
        return head1;
    }
    Node mergeHead = null;
    if (head1.data <= head2.data) {
        mergeHead = head1;
        head1 = head1.next;
        mergeHead.next = null;
    } else {
        mergeHead = head2;
        head2 = head2.next;  //注意链表的指针指向，这里的顺序不能错了。只有head指向下一个元素之后，mergeHead的next才能断开
        mergeHead.next = null;
    }
    Node mergeCur = mergeHead;
    while (head1 != null && head2 != null) {
        if (head1.data <= head2.data) {
            mergeCur.next = head1;
            head1 = head1.next;
            mergeCur = mergeCur.next;
            mergeCur.next = null; //使merge结果与原head1后面的元素断开。
        } else {
            mergeCur.next = head2;
            head2 = head2.next;
            mergeCur = mergeCur.next;
            mergeCur.next = null; //使merge结果与原head2后面的元素断开。
        }
    }
    if (head1 != null) {
        mergeCur.next = head1;
    } else if (head2 != null) {
        mergeCur.next = head2;
    }
        return mergeHead;
}

递归合并

用递归的方法代码更简洁，也可读性也很强。但是，两个链表比较长的时候，递归层次也可能会很深，结果造成栈溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 两个有序单链表合并
 * @param head1 第1个有序链表
 * @param head2 第2个有序链表
 * @return Node 归并之后的结果链表 ，若两个链表都为null，则返回null
 */
public static Node mergeSortedLinklist2(Node head1, Node head2) {
    if (head1 == null) {
        return head2;
    }
    if (head2 == null) {
        return head1;
    }
    Node mergeHead = null;
    if (head1.data <= head2.data) {
        mergeHead = head1;
        mergeHead.next = mergeSortedLinklist2(head1.next, head2);
    } else {
        mergeHead = head2;
        mergeHead.next = mergeSortedLinklist2(head1, head2.next);
    }
    return mergeHead;
}

判断两个单链表是否相交

如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。相当于“Y”字型的两个链表。
思路：只需要判断两个链表的最后一个节点是否相同即可。这样，只需要比较一次，但两个链表都遍历到尾部，时间复杂度为O(len1+len2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * -----判断两个单链表是否相交------
 * test: (null, null), (null, head2),(head1, null), (head1和head2相交), (head1和head2不相交)
 *
 * @param head1 链表1
 * @param head2 链表2
 * @return boolean。 true：两个链表相交； false：两个链表不相交
 */
public static boolean isLinkListIntersect(Node head1, Node head2) {
    if (head1 == null || head2 == null) return false;
    Node tail1 = head1;
    Node tail2 = head2;
    while (tail1.next != null) {
        tail1 = tail1.next;
    }
    while (tail2.next != null) {
        tail2 = tail2.next;
    }
    return tail1 == tail2;
}

获取两个单链表相交的结点

若两个链表相交，则获取相交处的结点。 即“Y”的交点
思路：如果有交点，则两个链表从交点到尾部一定是相同的元素，而且这段距离小于或等于最短的链表。

  • 则可以定义两个指针pFront和pBack，pBack指向较短链表的首部，pFront指向较长链表的lenLong- lenShort位置
  • 两个指针同时移动，直到找到相同结点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    /**
     * 获取两个单链表相交的结点
     * test:(null, null), (null, head2),(head1, null), (head1和head2相交), (head1和head2不相交)
     *
     * @param head1 链表1
     * @param head2 链表2
     * @return Node 返回两个链表相交的结点。若没有相交，则返回null
     */
    public static Node getCommonNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) return null;
        int len1 = 1;
        int len2 = 1;
        Node tail1 = head1;
        Node tail2 = head2;
        while (tail1.next != null) {
            tail1 = tail1.next;
            ++len1;
        }
        while (tail2.next != null) {
            tail2 = tail2.next;
            ++len2;
        }
        if (tail1 != tail2) {
            return null;//不相交
        }
        Node pFront = null;
        Node pBack = null;
        int distance = 0;
        //确定head1和heda2哪个比较长，pBack指向短的链表表头
        if (len1 <= len2) {
            pBack = head1;
            pFront = head2;
            distance = len2 - len1;
        } else {
            pBack = head2;
            pFront = head1;
            distance = len1 - len2;
        }
        //让pFront指向lenLong-lenShort的位置
        for (int i = 0; i < distance; i++) {
            pFront = pFront.next;
        }
        //两个指针同时向链表尾部移动，直到找到交点。
        while (pBack != pFront) {
            pBack = pBack.next;
            pFront = pFront.next;
        }
        return pFront;
    }

判断单链表是否有环

如果链表有环，单用一个指针是永远无法遍历到尾部的。那么，判断是否有环的思路，仍然是两个指针。
思想：

  • 定义两个指针都指向head
  • 一个指针一次走两步，另一个指针一次走一步。
  • 如果两个指针指到了同一个元素，证明有环。
    该算法的时间复杂度是O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * 判断单链表是否有环
     * test：(null), (偶数个元素、偶数环元素的链表)， （偶数个元素且无环的链表），(奇数个元素、奇数环的链表)，
     * （奇数个元素且无环的链表），（1个元素的无环链表），（1个元素有环链表），（只有2个元素且有环的链表），（圈链表）
     * @param head 待判断是否有环的链表
     * @return boolean 是否有环。false：无环。true：有环
     */
    public static boolean hasCycle(Node head) {
        if (head == null || head.next == null) return false;
        Node p1 = head;
        Node p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;//这一步需要考虑健壮性。即如果p2.next为null，则p2.next.next就会报异常。所以，要保证p2.next不为null
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }

判断有环单链表中，环的长度

思想：可以利用hasCycle的思路，如果找到相遇的结点了。那么p2从相遇的结点开始，再次走到此结点时走的距离，就是环的长度了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * 判断有环单链表中，环的长度
 * test：(null), (偶数个元素、偶数环元素的链表)， （偶数个元素且无环的链表），(奇数个元素、奇数环的链表)，
 * （奇数个元素且无环的链表），（1个元素的无环链表），（1个元素有环链表），（只有2个元素且有环的链表），（圈链表）
 * @param head 待计算环长度的链表
 * @return int 若有环，返回环的长度；若无环，返回0；
 */
public static int cycleLength(Node head) {
    if (head == null || head.next == null) return 0;
    Node p1 = head;
    Node p2 = head;
    Node kNode = null;//p1和p2相遇时的结点。
    //p1和p2相遇
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p1 == p2) {
            kNode = p2;
            break;
        }
    }
    //若p1和p2没有相遇，证明没有环
    if (p2 == null || p2.next == null) return 0;
    //再次移动p2一圈，计算环长度
    int length = 1; //先包括p2结点
    while (p2.next != kNode) {
        p2 = p2.next;
        ++length;
    }
    return length;
}
``` 
---
#### 获取单链表中，环的起始结点 
若单链表中存在环，则返回环的起始结点。这个问题可以有三种思路：
1. 利用环长度的方法计算。
2. 从交点和相遇点推导步长规律。
3. 配合HashSet一次遍历
##### 利用环长度的方法计算
利用环长度的方法计算比较简单
- 定义两个指针pFront和pBack。
- 假设环的长度为cycleLength，先让pFront走cycleLength步
- 让pBack指向head
- 两个指针同时移动，直到相遇，此时相遇的结点就是环的起始节点。*想不明白的动手画画就知道了。*
```java
 /**
 * 获取单链表中，环的起始结点
 * test：(null), (偶数个元素、偶数环元素的链表)， （偶数个元素且无环的链表），(奇数个元素、奇数环的链表)，
 * （奇数个元素且无环的链表），（1个元素的无环链表），（1个元素有环链表），（只有2个元素且有环的链表），（圈链表）
 * @param head 待处理的链表
 * @return Node 环的起始结点。 若没有环，则返回null
 */
public static Node getCycleStartNode1(Node head) {
    int cycleLength = cycleLength(head);
    if (cycleLength == 0) {
        return null; //环长度为0
    } else {
        Node pFront = head;
        Node pBack = head;
        for (int i = 0; i < cycleLength; i++) {
            pFront = pFront.next;
        }
        while (pFront != pBack) {
            pFront = pFront.next;
            pBack = pBack.next;
        }
        return pFront;
    }
}

从交点和相遇点推导步长规律

思想：对于有环链表，我们假设用环的起始结点startNode和相遇结点kNode(用hasCycle方法模拟走一下就知道了)，将链表分为3段。分别是k1，k2，k3.具体见下图：
linkList

假设判断其相遇时（hasCycle方法），一共走了k步。那么

  • p1走的步数：k1 + k2 = k;
  • p2走的步数：k1 + 2K2 + k3 = 2k;
    这样，两个公式联立就得k1 = k3.
    换句话说，当两个结点相遇的时候，将p1再重新指向head，p1和p2一起往后移动，当再次相遇的时候，该结点就是环的起点。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    /**
     * 获取单链表中，环的起始结点
     * test：(null), (偶数个元素、偶数环元素的链表)， （偶数个元素且无环的链表），(奇数个元素、奇数环的链表)，
     * （奇数个元素且无环的链表），（1个元素的无环链表），（1个元素有环链表），（只有2个元素且有环的链表），（圈链表）
     *
     * @param head 待处理的链表
     * @return Node 环的起始结点。 若没有环，则返回null
     */
    public static Node getCycleStartNode2(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node p1 = head;
        Node p2 = head;
        //找到相遇的结点。
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                break;
            }
        }
        if (p2 == null || p2.next == null) return null; //没有环
        //将p1重新指向head，p1和p2一起走，直到两个指针再次相遇
        p1 = head;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
配合HashSet一次遍历

思想：可以在遍历的时候，将链表结点放入HashSet中，当遍历时发现有此元素，则该结点就是环的起始结点。这种方法很简洁，但是当结点比较多的时候，空间开销太大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 获取单链表中，环的起始结点
 *
 * @param head 待处理的链表
 * @return Node 环的起始结点。 若没有环，则返回null
 */
public static Node getCycleStartNode3(Node head) {
    if (head == null || head.next == null) {
        return null;
    }
    HashSet nodeSet = new HashSet();
    Node p = head;
    while (p != null && !nodeSet.contains(p)) {
        nodeSet.add(p);
        p = p.next;
    }
    //如果无环，此时p == null，如果有环，此时p指向环的起始结点。
    return p;
}

删除单链表中指定结点

这个问题有个特殊要求，就是要求时间复杂度O(1)
常规的思路：对于这样一段链表：n0 -> n1 -> n2 -> n3 -> n4 如果要删除结点n2，可以让n1指向n3。然后释放n2。这样的话需要找到结点n1，时间复杂度为O(n)

思想：对于单链表，可以将n3复制到n2，然后删除n3即可。这样的方法在java中，如果是删除链表最后一个元素，仍然需要找前面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 删除单链表中指定结点
 * test:(null,null),(d1, null),(null, d2),(链表中间的结点) ，(链表结尾的结点)，（链表的头结点）
 *
 * @param head         待删除的链表
 * @param nodeToDelete 待删除结点
 */
public static void deleteNode(Node head, Node nodeToDelete) {
    if (head == null || nodeToDelete == null) {
        return;
    }
    if (head.next == null && nodeToDelete == head) {//当链表只有1 个元素，并且删除此元素
        head = null;
    }
    //如果nodeToDelete是最后一个结点，或链表只有1个结点。则直接置为null，倒数第2个结点的next就指向了null
    if (nodeToDelete.next != null) {  //删除中间结点
        nodeToDelete.data = nodeToDelete.next.data;
        nodeToDelete.next = nodeToDelete.next.next;
    } else { //删除链表最后一个结点
        Node preNode = head;
        while (preNode.next != nodeToDelete) {
            preNode = preNode.next;
        }
        preNode.next = null;
    }
}

好了，先总结到这里吧。

参考资料：

http://blog.csdn.net/fightforyourdream/article/details/16353519
http://www.jb51.net/article/71885.htm