链表-常见面试问题总结

发表于

最近这段时间都在忙活校招，在面试的过程中遇到了很多有关链表的问题，由于以前没怎么搞过ACM，数据结构也忘的七七八八了，所以总体感觉回答得不是很好。昨天把链表的基础回顾了下，见这里单链表的基础操作，于是今天把面试过程中经常遇到的链表相关的问题总结下。

翻转

单链表的反转是面试的常用考点，所以必须掌握。思路是把当前节点拿过来作为已经翻转的表头，成为一个已翻转的子链，用result指向其头部（也就是当前节点）。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 反转单链表
public static Node traversingReverse(Node head) {
	Node result = null;
	Node temp = null;
	// 头反转法：把当前节点拿过来作为已经翻转结果的表头
	while (head != null) {
		temp = head.next; // 保存下一个节点
		head.next = result; // 当前节点放在结果的开头
		result = head; // 当前节点的头
		head = temp; // head指向下一个节点
	}
	return result;
}

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

有一种情况，当我们的now引用指向某一个节点的时候，我们需要删除该节点。然而如果不知道now节点的前驱节点，一般方法是无法删除now这个节点的。

这个时候，我们可以使用“懒”删除，这种方法的思想是：把now节点后驱节点的值赋给now节点，然后now节点的next指向的它后驱节点的下一个节点。因为不用遍历，所以这个算法的时间复杂度是O(1)。然而要注意的是尾节点，当now节点就是尾节点的时候，这种办法就行不通了。

代码如下：

1
2
3
4
5
6
7
8
9
// O(1)复杂度删除某个节点
public static void lazyDelete(Node now) {
    if(now.next != null) { // ①非尾节点
        now.value = now.next.value; // 复制后驱节点的值
        now.next = now.next.next; // “删除”后驱节点
    }  else{ // ②尾节点，行不通
        return;
    }
}

求链表倒数第k个节点

经常会遇到求单链表倒数第几个节点的问题，如果按常规方法的话，我们需要先遍历整个链表，记录下节点个数，假设为n，然后再遍历一遍，第n-k+1个就是所求节点了。可是这个方法效率太低，需要两次遍历，有没有更加高效的方法呢？答案是肯定的。我们可以用 快慢指针 来解决这个问题，这个方法的思想是这样的：

  • 假设有引用fast、slow，开始都指向首节点;
  • fast先走k次，这样fast和slow就相隔了k个节点;
  • 然后fast、slow一起走，当fast走到链表末尾为null的时候，slow就是所求节点了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 求单链表倒数第k个节点
public static Node getKNode(Node head, int k) {
    Node fast = head;
    Node slow = head;
    
    int i = 0;
    for(; i < k && fast != null; i++) {
        fast = fast.next;
    }
    
    if(i != k) {
        System.out.println(k + "位置超出链表长度");
    }
    
    while(fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    return slow;
}

求链表的中间节点

如果要求一个链表的中间节点，常规的方法是先遍历一次获取链表的长度n，如果n是偶数就n/2、n/2+1都可以，如果n是奇数，那就第n/2+1个。可是这个方法的效率也是非常低。

其实通过上面找用快慢指针的方法来找倒数第k个数，我们可以衍生到这里来。这个方法的思路是这样的：

  • 假设有引用fast、slow，开始都指向首节点;
  • fast、slow同时走，但是fast每次走2步，slow每次走1步；
  • 当fast走到链表末尾时，slow就是中间节点；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 求链表的中间节点
public static Node getMiddleNode(Node head) {
    if (head == null) {
        return null;
    }
    
    Node fast = head;
    Node slow = head;
    
    // ①如果fast==null的话，说明是偶数个；而fast.next==null的话，说明是奇数个
    // ①条件返回的是偶数情况中的后者，如果要返回前者，可用下面判断条件：
    // while (fast != null && fast.next != null && fast.next.next != null)
    while (fast != null && fast.next != null) { // ①
        fast = fast.next.next; // 快指针走2步
        slow = slow.next; // 慢指针走1步
    }
    
    return slow;
}

单链表是否存在环(leetcode 141)

其实判断单链表是否有环有2种方法，第一种是用Set集合的方法，第二种是用快慢指针的方法。

利用HashSet集合

这个方法的思想很简单，就是遍历该链表，每走一次，就判断HashSet中是否存在该节点，如果存在则说明有环，结束；如果不存在，说明还没有环，把该节点放到HashSet中去，直到链表的末尾。如果利用的是HashSet，则该算法的时间复杂度也是O(n)，就是空间复杂度大了点。

代码如下：

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
// 利用HashMap判断是否有环
public static boolean hasCircle(Node head) {
    Set<Node> set = new HashSet<>();
    while (head != null) {
    	if(getFromSet(set, head) != null) {
    		return true;
    	}
    	
    	set.add(head);
    	head = head.next;
    }
    return false;
}
// 由于Set没有提供get()方法，所以自己实现一个
// 缘何Set不提供get()？？？
public static Node getFromSet(Set<Node> set, Node node) {
	Iterator it = set.iterator();
	Node tmp;
	while(it.hasNext()) {
		tmp = (Node)it.next();
		if(tmp == node) {
			return tmp;
		}
	}
	return null;
}

利用快慢指针

上面的方法实现起来很简单高效，但是却需要额外的空间，空间复杂度是O(n)，而快慢指针是一个更高效的方法。让快指针每次走2步，慢指针每次走1步，两个指针的速度不一样，如果存在环的话，那么最后快慢指针肯定会相遇。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 利用快慢指针判断链表是否有环
public static boolean hasCircle(Node head) {
    Node fast = head;
    Node slow = head;
    
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == slow) {
            return true;
        }
    }
    
    return false;
}

单链表中环的起点(leetcode 142)

快慢指针求环起点
假设链表中存在环，我们先设定几个参数：n(环的长度=7)、a(链表起点到环起点的距离=3)、x(fast指针到环起点的时候，slow指针在环中的位置0 <= x < n)，由此我们可以推出下面几个性质：

  1. slow到起点(s3)的时候，fast在环中走了x步(f3)，那么fast和slow相差 n - x 步，也就是说 n - x 步后，fast会追上slow；
  2. 经过 n - x 步后(4步)，fast和slow在环中M点相遇(f7与s7)；
  3. 假设这时候相遇点M与环起点的距离为b(=4)，则slow走过的距离是 a + b ，而fast走过的距离为 a + b + k n 。显然fast走的长度是slow的2倍，所以2 ( a + b ) = a + b + k n，则 **a + b = k n**；
  4. 把fast指针拉回链表的起始点，这时候fast和slow每次都走一步，经过a步后，fast和slow在环的起始点相遇。

代码如下：

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
// 使用快慢指针求环起点
public static Node listCircleStart(Node head) {
    // 空链或者单节点，不存在环
    if(head == null || head.next == null) {
        return null;
    }
    
    Node fast = head;
    Node slow = head;
    
    do {
        if (fast == null || fast.next == null) { // 无环
            return null;
        }
        
        fast = fast.next.next; // 走2步
        slow = slow.next; // 走1步
    } while (fast != slow) // 直到fast和slow相遇
    
    fast = head; // 重新拉回链表起点
    while (fast != slow) { // 相遇即为环起点
        fast = fast.next; // 走1步
        slow = slow.next; // 走1步
    }
    
    return fast;
}

单链表中环的长度

在上面，我们找到环的起点后，再用slow指针走一遍，就可以算出环的长度了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 使用快慢指针求环长度
public static int listCircleLength(Node head) {
    Node cicleStart = listCircleStart(head); // 先利用上面的方法求出环起点
    
    if(cicleStart == null) {
        return 0;
    }
    
    Node tmp = cicleStart.next;
    int counter = 1;
    while (tmp != cicleStart) { // 重走一遍，直到回到环起点
        counter++;
        tmp = tmp.next;
    }
    
    return counter;
}

两个链表是否相交并求出交点(leetcode 160)

给定2个链表，判断这两个链表是否相交，如果相交的话，就类似于一个向左翻转90°的Y。见下图：
相交链表

这个问题相比环来说简单很多，我们可以用Set集合方法、链长先走方法、成环方法来解决。下面我们逐一来看。

Set集合方法

这个方法的思路最简单：

  1. 先遍历a链，依次把所有节点放入到Set中去；
  2. 然后遍历b链，每到一个节点，就去Set看是否存在该节点，如果存在，则说明有交点，而交点就是该节点(第一个相等的肯定是交点)；
  3. 如果直到b链的末尾都没有相等节点，则说明没有交点；

这个方法其实比较笨，效率也比较低。

代码如下：

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
// 利用Set求2链表交点
public static Node getCrossNode(Node headA, Node headB) {
    Set<Node> set = new Hash<>();
    
    // 把a链全部放入Set中
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }
    
    // 遍历b链
    while (headB != null) {
        if(set.getFromSet(set, headB) != null) { // 相交
            return headB;
        }
    }
    
    return null;
}
public static Node getFromSet(Set<Node> set, Node node) {
	Iterator it = set.iterator();
	Node tmp;
	while(it.hasNext()) {
		tmp = (Node)it.next();
		if(tmp == node) {
			return tmp;
		}
	}
	return null;
}

链长先走方法

这个方法的思路是这样的：

  1. 遍历一次，求出链a的长度x，链b的长度y，求出|x-y|=k，这个k是链a和链b的长度差；
  2. 让长的链先走k步，这样a、b链剩下的长度都是一样的；
  3. 然后a、b一起走，遇到相等的节点，就是它们的交点；如果没相遇，说明没有交点；

这个方法比Set的方法好很多，因为不用用到Set集合，所以快很多。

代码如下：

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
// 链长先走求2链交点
public static Node getCrossNode(Node headA, Node headB) {
    int x = 0; // 链a长度
    int y = 0; // 链b长度
    
    Node tmp = headA; // 因为后续还要用到headA，所以用临时变量来遍历
    while(tmp != null) {
        x++;
        tmp = tmp.next;
    }
    tmp = headB;
    while(tmp != null) {
        y++;
        tmp = tmp.next;
    }
    
    int k; // 链长度差
    if (x - y > 0) { // a链长
        k = x - y;
        
        // a链走k步
        for (int i = 0; i < k; i++) {
            headA = headA.next;
        }
    } else {
        k = y - x;
        
        // b链走k步
        for (int i = 0; i < k; i++) {
            headB = headB.next;
        }
    }
    
    // 这时候，headA指向的子链和headB指向的子链长度一样，一起走
    while (headA != null) { // 这里不需要判断headB，因为headA和headB肯定同时为null
        if(headA == headB) { // 相遇的节点是交点
            return headA
        }
        
        headA = headA.next;
        headB = headB.next;
    }
    
    return null;
}

成环方法

我们把a链的首尾连接起来，这样a链就形成了一个环。如果a、b链相交，那么从b链来看，链b这个时候就会出现环路，我们可以用上面找环的方法来解决。如下图：
成环方法求两链交点

这个方法的思路如下：

  1. 把a链的尾部指向a链头部，让其形成一个环；
  2. 从b链头部开始遍历，如果b中能找到环，说明ab相交，环的起点即为交点；如果不能找到环，说明无交点；
  3. 把a链中的环断开，恢复链a；

这个方法的代码和找环的代码差不多，这里就不写了。

复制带有随机指针的链表(leetcode 138)

一个单链表除了next指针外，还有一个random指针，random指针随机指向任何一个元素(可能为null)，然后我们的任务是复制它。

这个复制其实next指针直接用常规方法就能解决，难点在于random指针，因为我们不知道random指针在复制后的地址-复制元素的地址变了，而且random指向的元素可能还没生成。

要解决这个问题，我们有2种方法：map集合方法、“副本”方法。

map集合方法

这个方法的思路是这样的：

  1. 先遍历一次原链，用常规方法复制一个新链，使其next指针指向正确的位置，random指针为null；而且在这个过程中，每生成一个新节点，用map来保存旧节点到新节点的映射，类似与map(oldNode, newNode);
  2. 再同时遍历原链和新链，在原链中得到节点的random指向的oldNode，然后利用map.get(oldNode)获取newCode，把新链节点的random指向这个newNode；

结合下图：
利用map复制带random的链表

容易知道，这个方法的时间复杂度是O(n)，空间复杂度也是O(n)，效率比较低。

代码如下：

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
// 利用map实现带random指针的链表复制
public static NodeWithRandom copyWithRandom (NodeWithRandom h) {
	NodeWithRandom newNode = null;
	Map<NodeWithRandom, NodeWithRandom> map = new HashMap<>();
	map.put(null, null); // 解决random指向null的情况
	// 先用常规方法复制链表
	NodeWithRandom tmp1 = h;
	NodeWithRandom h2 = null;
	while (tmp1 != null) {
		if(newNode == null) { // 表头
			newNode = new NodeWithRandom(tmp1.value);
			h2 = newNode;
		} else {
			newNode.next = new NodeWithRandom(tmp1.value);
			newNode = newNode.next;
		}
		map.put(tmp1, newNode); // 旧地址到新地址的映射
		tmp1 = tmp1.next;
	}
	// 再两个链表同时走复制random，a'.random = map[a.random]
	tmp1 = h;
	NodeWithRandom tmp2 = h2;
	while (tmp1 != null) {
		tmp2.random = map.get(tmp1.random); // 利用map的映射，将新链表的random指针指向新节点
		tmp1 = tmp1.next;
		tmp2 = tmp2.next;
	}
	return h2;
}
// 带random的节点
class NodeWithRandom {
	public int value;
	public NodeWithRandom next;
	public NodeWithRandom random;
	public NodeWithRandom (int value) {
		this.value = value;
		this.next = null;
		this.random = null;
	}
}

“副本”方法

这个方法的思路主要是：

  1. new副本：在每个旧节点后插入一个当前节点的副本，重新拉成链；
  2. 复制random：新节点的random=旧节点random的next；
  3. 拆分：奇数项都是旧节点，偶数项都是新节点，提取偶数项成链；

如下图：
“副本”方法复制带随机指针的链表

代码如下：

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
// "副本"方式复制带随机指针链表
public static NodeWithRandom copyRandomList (NodeWithRandom head) {
	if (head == null) {
		return null;
	}
	// 在每个节点后创建副本，拉成链
	NodeWithRandom now = head; 
	while (now != null) {
		NodeWithRandom copy = new NodeWithRandom(now.value);
		copy.next = now.next;
		now.next = copy;
		now = copy.next;
	}
	// 复制random
	for (now = head; now != null; now = now.next.next) {
		now.next.random = now.random == null ? null : now.random.next; // 新节点的random=旧节点random的next
	}
	// 奇数项为旧节点，偶数项为新节点
	// 提取出偶数项就是所求
	NodeWithRandom h = head.next; // 新链头部
	NodeWithRandom t = h; // 遍历游标
	NodeWithRandom tail = head;
	for (;;) {
		tail.next = t.next; // 重连旧节点
		tail = tail.next; // 移向下一个旧节点
		if(tail == null) {
			break;
		}
		t.next = tail.next; // 连接新节点
		t = t.next; // 移向下一个新节点
	} 
	return h;
}

链表partition过程(leetcode 86)

链表里存放整数，给定x，把x小的节点放在>=x之前，这就是一个partition过程，数组在partition的过程就是这样做的。然而链表和数组不同的是，在patition的过程中，链表没必要赋值来赋值去，而是重新起一个头，把比x小的连起来，把>=x的连成另外一条链，最后再把这2条链连起来就是了。

代码如下：

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
// 链表的partition过程
public static Node(Node head, int x) {
    Node h1 = null; // 小子链头部
    Node h2 = null; // 大子链头部
    Node t1 = null; // 小子链尾部
    Node t2 = null; // 大子链尾部
    
    for (; head != null; head = head.next) {
        if (head.val < x) { // 比x小
            if (h1 = null) { // 头部
                h1 = head;
                t1 = head;
            } else {
                t1.next = head;
                t1 = t1.next;
            }
        } else {
            if (h2 == null) {
                h2 = head;
                t2 = head;
            } else {
                t2.next = head;
                t2 = t2.next;
            }
        }
    }
    
    if (t2 != null) { // 大子链有节点
        t2.next = null;
    }
    if(t1 != null) { // 小子链有节点
        t1.next = h2;
    }
        
    return h1 != null ? h1 : h2;    
}

总结

从上面可以看出，涉及链表的问题，大部分都可以用快慢指针或集合的方式来解决，所以遇到这种问题可以往这方面考虑。由于链表实在非常灵活，所以具体的问题还是得灵活处理。

参考文档