链表的几个问题

发表于   |  

链表的几个问题和答案的代码实现。

简单链表的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class LkList<T> {

        Node header;

        public LkList() {
            this.header = null;
        }

        public void add(T v) {
            Node n = new Node(v, header);
            header = n;
        }

        private class Node {
            T item;
            Node next;

            public Node(T item, Node next) {
                this.item = item;
                this.next = next;
            }
        }

    }

给出单链表中一个节点的指针p（不是最后的那个节点），删除该节点

思路：由于是单链表，所以无法得到该节点的前一个节点，但是我们可以容易地得到该节点之后的节点。所以要是删除该节点之后的节点，我们是可以容易做到的。对于删除节点，其实就是将该节点的数据从链表中删除，而对于该节点本身在不在链表中我们并不关心。所以我们可以想到，为了删除本节点的数据，我们可以用其他数据覆盖掉本节点的数据，我们可以用该节点之后的节点的数据覆盖掉本节点的数据，然后将之后的那个节点删除，这样就相当于删除了本节点。就是下图显示的那样。

link1

代码实现：

1
2
3
4
5
6
7
public LkList.Node deleteNode(LkList.Node p) {
    LkList.Node deleted = p.next; 
    p.item = deleted.item;
    p.next = deleted.next;
    deleted.next = null;
    return deleted;
}

单链表的转置

思路：对该单链表进行遍历，对于每个节点，进行头插法，插入到另一个链表，然后将该链表返回。

代码实现

1
2
3
4
5
6
7
8
9
10
11
public LkList<Integer> reverseList(LkList<Integer> list) {
    LkList<Integer> nl = new LkList<>();
    LkList.Node p;
    while (list.header != null) {
        p = list.header.next;
        list.header.next = nl.header;
        nl.header = list.header;
        list.header = p;
    }
    return nl;
}

求单链表倒数第k个节点

思路：

  1. 求倒数第k个节点，就相当于第len-k+1(len是单链表的长度)个节点，所以可以先遍历一遍链表，求出链表的长度，然后再求第len-k+1个节点。

  2. 求倒数第k个节点，也就是说求一个节点，该节点距离链表的末尾k个距离，那么，问题就是如何测量这段距离，我们可以使用一个指针p1,从头遍历到第k+1个节点，那么从开始节点到p1指向的节点就的距离相差k，我们可以把这段距离当作一把尺来测试每个节点是否到链表末尾距离为k。所以，方法就是：可以使用两个指针p1,p2，先让p1遍历到第k+1个节点，然后p1，p2一起向后遍历，当p1遍历到末尾null时，p2指向的节点就是倒数第k个节点。

比如说想要求倒数第3个节点，我们可以先让p1遍历到第4个节点（节点6），然后p1,p2一起往后遍历，直到p1到null，此时，p2指向的节点就是倒数第3个节点。

link2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * assume k is less than the size of list
 */
public static LkList.Node lastKth(LkList<Integer> list, int k) {
    LkList.Node p1 = list.header;
    LkList.Node p2 = list.header;
    for (int i = 0; i < k && p1 != null; i++) {
        p1 = p1.next;
    }
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

求链表的中间节点

思路：看着与上面那题挺相似的，但是我们中间那个节点是第几个节点我们并不知道，单是中间节点是挺特殊的位置，正好是整个链表的一半。可以使用两个指针，一个一次遍历一个节点，另一个一次遍历两个节点。这样就能找到中间节点。需要的注意的是当链表中的节点是奇数个和偶数个的区别。

奇数个的情况：
link3

偶数个的情况：
link4

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static LkList.Node findMidNode(LkList<Integer> list) {
    LkList.Node p1 = list.header;
    LkList.Node p2;
    if (p1 == null) { // 链表为空
        return null;
    } else if (p1.next == null) { //链表只有一个节点
        return p1;
    }
    p2 = p1.next;
    while (p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
        if (p2.next == null) { //链表有偶数个节点的时候，p2走到最后一个节点
            break;
        }
        p2 = p2.next;
    }
    return p1;
}

判断两个链表是否相交

思路：判断两个链表的最后一个节点是否是同一个节点

link6

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isIntersect(LkList<Integer> lk1, LkList<Integer> lk2) {
    LkList.Node p1 = lk1.header;
    LkList.Node p2 = lk2.header;
    if (p1 == null || p2 == null) return false;
    while (p1.next != null) {
        p1 = p1.next;
    }
    while (p2.next != null) {
        p2 = p2.next;
    }
    return p1 == p2;
}

求两链表相交的交点

思路：求出两个链表的长度差k，然长的链表先遍历k个节点，然后两个链表一起遍历，直到遍历到同一个节点，这个节点就是两个链表相交的交点。

link7

代码实现

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
public LkList.Node findIntersect(LkList<Integer> lk1, LkList<Integer> lk2) {
    LkList.Node p1 = lk1.header;
    LkList.Node p2 = lk2.header;
    if (p1 == null || p2 == null) return null;
    int len1 = 1;
    int len2 = 1;
    while (p1.next != null) {
        p1 = p1.next;
        len1++;
    }
    while (p2.next != null) {
        p2 = p2.next;
        len2++;
    }
    if (p1 != p2) return null;
    int k = Math.abs(len1 - len2);
    p1 = lk1.header;
    p2 = lk2.header;
    if (len1 > len2) {
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0; i < k; i++) {
            p2 = p2.next;
        }
    }
    while (p1 != null && p2 != null && p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

判断单链表是否存在环

思路：

  1. 使用HashSet来保存遍历过的节点，在遍历新节点的时候，进行查询是否之前遍历过，如果遍历过，就表示有环，能遍历完整个链表就表示没有环。
  2. 使用两个指针，一个每次遍历一个几点，另一个每次遍历两个节点，如果有环，则，在某一次遍历后两个节点会相遇，如果没有环，快的那个节点会变为null。对于有环的链表，两个指针总会在环中循环遍历，遍历速度快的那个指针每次比慢的多遍历一个节点，在某一个时间点，快的指针会将慢的指针套圈（就像跑步一样，跑的快的会将跑的慢的套圈。），两个指针相遇。

代码实现

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
//两个指针的方式
public boolean hasCircle(LkList<Integer> list) {
    LkList.Node p1 = list.header;
    if (p1 == null) return false;
    LkList.Node p2 = list.header.next;
    LkList.Node node = getMeetNode(p1, p2);
    return node != null;
}

private LkList.Node getMeetNode(LkList.Node p1, LkList.Node p2) {
    while (p1 != null && p2 != null) {
        p1 = p1.next;
        p2 = p2.next;
        if (p2 != null) {
            p2 = p2.next;
        }
        if (p1 == p2) {
            return p1;
        }
    }
    return null;
}

//使用HashSet
public boolean hasCircleUseSet(LkList<Integer> list) {
    HashSet<LkList.Node> set = new HashSet<>();
    LkList.Node p = list.header;
    while (p != null) {
        if (set.contains(p)) {
            return true;
        }
        set.add(p);
        p = p.next;
    }
    return false;
}

找到环的入口

思路：

  1. 与上一题的方法一一样，还是使用HashSet，第一个遍历过的节点就是入口。
  2. 只有两个指针，先使用上面的方法二找到两个指针相遇的节点m，设入口节点为n,第一个节点为h,我们使用一个指针p1,从h遍历到m,计算出h到m的长度x,然后使用指针p2从m节点开始遍历，遍历一圈环，计算出环的长度y,计算出|x-y|,这个差值就是hn与mn的长度差，如果hn较长，则p1从h开始先遍历|x-y|个节点，然后p1和p2（指向m）开始一起遍历，当p1和p2遍历到同一个节点时，这个节点就是环的入口，对mn较长的情况同理。

link5

代码实现

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
//使用两个指针方式
private static LkList.Node findIntersection(LkList<Integer> list) {
    if (!hasCircle(list)) {
        return null;
    }
    LkList.Node p1 = list.header;
    LkList.Node p2 = list.header;
    LkList.Node node = getMeetNode(p1, p2);
    int len1 = 0;
    while (p1 != node) {
        len1++;
        p1 = p1.next;
    }

    p2 = node.next;
    int lenCircle = 1;
    while (p2 != node) {
        lenCircle++;
        p2 = p2.next;
    }
    
    p1 = list.header;
    int diffLen = Math.abs(len1 - lenCircle);
    if (len1 > lenCircle) {
        for (int i = 0; i < diffLen; i++) {
            p1 = p1.next;
        }
    } else {
        for (int i = 0; i < diffLen; i++) {
            p2 = p2.next;
        }
    }
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}
//使用HashSet方式
private static LkList.Node findIntersectionUseSet(LkList<Integer> list) {
    if (!hasCircle(list)) {
        return null;
    }
    HashSet<LkList.Node> set = new HashSet<>();
    LkList.Node p = list.header;
    while (p != null) {
        if (set.contains(p)) {
            return p;
        }
        set.add(p);
        p = p.next;
    }
    return null;
}

链表有环，如何判断相交

思路：和判断链表是否有环同样的方式。分别对两个链表进行判断是否有环，如果两个都有环，再对其中一个链表的环中的一个节点判断是否再另一个链表的环中即可。

代码实现

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
/*
判断两个链表（链表可能有环）是否相交
 */
public boolean intersect(LkList<Integer> lk1, LkList<Integer> lk2) {
    
    boolean lk1hasCircle = true;
    boolean lk2hasCircle = true;
    
    LkList.Node p11 = lk1.header;
    if (p11 == null) return false;
    LkList.Node p12 = lk1.header;
    while (p11 != null && p12 != null) {
        p11 = p11.next;
        p12 = p12.next;
        if (p12 != null) {
            p12 = p12.next;
        }
        if (p11 == p12) {
            break;
        }
    }
    if (p11 != p12) {
        lk1hasCircle = false;
    }
    LkList.Node p21 = lk2.header;
    if (p21 == null) {
        return false;
    }
    LkList.Node p22 = p21.next;
    while (p21 != null && p22 != null) {
        p21 = p21.next;
        p22 = p22.next;
        if (p22 != null) {
            p22 = p22.next;
        }
        if (p21 == p22) {
            break;
        }
    }
    if (p21 != p22) {
        lk2hasCircle = false;
    }
    
    if (!lk1hasCircle && !lk2hasCircle) { // 两个链表都没有环
        return isIntersect(lk1, lk2); //之前判断两个链表是否相交的方法
    } else if (lk1hasCircle && !lk2hasCircle || !lk1hasCircle) { //lk1hasCircle && !lk2hasCircle || !lk1hasCircle && lk2hasCircle  只有一个链表有环
        return false;
    }
    
    //两个都有环
    if (p11 == p21) {
        return true;
    }
    p21 = p21.next;
    while (p21 != p22) {
        if (p11 == p21) return true;
        p21 = p21.next;
    }
    return false;
}