哈希表来保存原节点与副本节点的对应关系，所以额外空间复杂度

首先介绍普通解法，普通解法可以做到时间复杂度为O (N )，额外空间复杂度为O (N )，需要使用到哈希表（HashMap）结构。具体过程如下：

1．首先从左到右遍历链表，对每个节点都复制生成相应的副本节点，然后将对应关系放入哈希表map中。例如，链表1->2->3->null，遍历1、2、3时依次生成1′、2′、3′，最后将对应关系放入map中：

key value 意义

1 1′ 表示节点1复制了节点1′

2 2′ 表示节点2复制了节点2′

3 3′ 表示节点3复制了节点3′

步骤1完成后，原链表没有任何变化，每一个副本节点的next和rand指针都指向null。

2．再从左到右遍历链表，此时就可以设置每一个副本节点的next和rand指针。

例如：原链表1->2->3->null，假设1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。遍历到节点1时，可以从map中得到节点1的副本节点1′，节点1的next指向节点2，所以从map中得到节点2的副本节点2′，然后令1′.next=2′，副本节点1′的next指针就设置好了。同时节点1的rand指向节点3，所以从map中得到节点3的副本节点3′，然后令1′.rand=3′，副本节点1′的rand指针也设置好了。以这种方式可以设置每一个副本节点的next与rand指针。

3．将1′节点作为结果返回即可。

哈希表增删改查的操作时间复杂度都是O (1)，普通方法一共只遍历链表两遍，所以普通解法的时间复杂度为O (N )，因为使用了哈希表来保存原节点与副本节点的对应关系，所以额外空间复杂度为O (N )。

具体过程请参看如下代码中的copyListWithRand1方法。

public Node copyListWithRand1(Node head) { HashMapmap = new HashMap(); Node cur = head; while (cur ! = null) { map.put(cur, new Node(cur.value)); cur = cur.next; } cur = head; while (cur ! = null) { map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } return map.get(head); }

接下来介绍进阶解法，进阶解法不使用哈希表来保存对应关系，而只用有限的几个变量完成所有的功能。具体过程如下：

1．首先从左到右遍历链表，对每个节点cur都复制生成相应的副本节点copy，然后把copy放在cur和下一个要遍历节点的中间。

例如：原链表1->2->3->null，在步骤1中完成后，原链表变成1->1′->2->2′->3->3′->null。

2．再从左到右遍历链表，在遍历时设置每一个副本节点的rand指针。还是举例来说明调整过程。

例如：此时链表为1->1′->2->2′->3->3′->null，假设1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。遍历到节点1时，节点1的下一个节点1.next就是其副本节点1′。1的rand指针指向3，所以1′的rand指针应该指向3′。如何找到3′呢？因为每个节点的副本节点都在自己的后一个，所以此时通过3.next就可以找到3′，令1′.next=3′即可。以这种方式可以设置每一个副本节点的rand指针。

3．步骤2完成后，节点1，2，3，……之间的rand关系没有任何变化，节点1′，2′，3′……之间的rand关系也被正确设置了，此时所有的节点与副本节点串在一起，将其分离出来即可。

例如：此时链表为1->1′->2->2′->3->3′->null，分离成1->2->3->null和1′->2′->3′->null即可。并且在这一步中，每个节点的rand指针不用做任何调整，在步骤2中都已经设置好。

4．将1′节点作为结果返回即可。

进阶解法考查的依然是利用有限几个变量完成链表调整的代码实现能力。具体过程请参看如下代码中的copyListWithRand2方法。

public Node copyListWithRand2(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; // 复制并链接每一个节点 while (cur ! = null) { next = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } cur = head; Node curCopy = null; // 设置复制节点的rand指针 while (cur ! = null) { next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand ! = null ? cur.rand.next : null; cur = next; } Node res = head.next; cur = head; // 拆分 while (cur ! = null) { next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next ! = null ? next.next : null; cur = next; } return res; }

两个单链表生成相加链表

【题目】

假设链表中每一个节点的值都在0～9之间，那么链表整体就可以代表一个整数。

例如：9->3->7，可以代表整数937。

给定两个这种链表的头节点head1和head2，请生成代表两个整数相加值的结果链表。

例如：链表1为9->3->7，链表2为6->3，最后生成新的结果链表为1->0->0->0。

【难度】

士　★☆☆☆

【解答】

这道题难度较低，考查面试者基本的代码实现能力。一种实现方式是将两个链表先算出各自所代表的整数，然后求出两个整数的和，最后将这个和转换成链表的形式，但是这种方法有一个很大的问题，链表的长度可以很长，可以表达一个很大的整数，因此转成系统中的int类型时可能会溢出，所以不推荐这种方法。

方法一：利用栈结构求解。

1．将两个链表分别从左到右遍历，遍历过程中将值压栈，这样就生成了两个链表节点值的逆序栈，分别表示为s1和s2。

例如：链表9->3->7，s1从栈顶到栈底为7，3，9；链表6->3，s2从栈顶到栈底为3，6。

2．将s1和s2同步弹出，这样就相当于两个链表从低位到高位依次弹出，在这个过程中生成相加链表即可，同时需要关注每一步是否有进位，用ca表示。

例如：s1先弹出7，s2先弹出3，这一步相加结果为10，产生了进位，令ca=1，然后生成一个节点值为0的新节点，记为new1; s1再弹出3，s2再弹出6，这时进位为ca=1，所以这一步相加结果为10，继续产生进位，仍令ca=1，然后生成一个节点值为0的新节点记为new2，令new2.next=new1; s1再弹出9，s2为空，这时ca=1，这一步相加结果为10，仍令ca=1，然后生成一个节点值为0的新节点，记为new3，令new3.next=new2。这一步也是模拟简单的从低位到高位进位相加的过程。

3．当s1和s2都为空时，还要关注一下进位信息是否为1，如果为1，比如步骤2中的例子，表示还要生成一个节点值为1的新节点，记为new4，令new4.next=new3。

4．返回新生成的结果链表即可。

具体过程请参看如下代码中的addLists1方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node addLists1(Node head1, Node head2) { Stacks1 = new Stack(); Stacks2 = new Stack(); while (head1 ! = null) { s1.push(head1.value); head1 = head1.next; } while (head2 ! = null) { s2.push(head2.value); head2 = head2.next; } int ca = 0; int n1 = 0; int n2 = 0; int n = 0; Node node = null; Node pre = null; while (! s1.isEmpty() || ! s2.isEmpty()) { n1 = s1.isEmpty() ? 0 : s1.pop(); n2 = s2.isEmpty() ? 0 : s2.pop(); n = n1 + n2 + ca; pre = node; node = new Node(n % 10); node.next = pre; ca = n / 10; } if (ca == 1) { pre = node; node = new Node(1); node.next = pre; } return node; }

方法二：利用链表的逆序求解，可以省掉用栈的空间。

1．将两个链表逆序，这样就可以依次得到从低位到高位的数字。

例如：链表9->3->7，逆序后变为7->3->9；链表6->3，逆序后变为3->6。

2．同步遍历两个逆序后的链表，这样就依次得到两个链表从低位到高位的数字，在这个过程中生成相加链表即可，同时需要关注每一步是否有进位，用ca表示。具体过程与方法一的步骤2相同。

3．当两个链表都遍历完成后，还要关注进位信息是否为1，如果为1，还要生成一个节点值为1的新节点。

4．将两个逆序的链表再逆序一次，即调整成原来的样子。

5．返回新生成的结果链表。

具体过程请参看如下代码中的addLists2方法。

public Node addLists2(Node head1, Node head2) { head1 = reverseList(head1); head2 = reverseList(head2); int ca = 0; int n1 = 0; int n2 = 0; int n = 0; Node c1 = head1; Node c2 = head2; Node node = null; Node pre = null; while (c1 ! = null || c2 ! = null) { n1 = c1 ! = null ? c1.value : 0; n2 = c2 ! = null ? c2.value : 0; n = n1 + n2 + ca; pre = node; node = new Node(n % 10); node.next = pre; ca = n / 10; c1 = c1 ! = null ? c1.next : null; c2 = c2 ! = null ? c2.next : null; } if (ca == 1) { pre = node; node = new Node(1); node.next = pre; } reverseList(head1); reverseList(head2); return node; } public Node reverseList(Node head) { Node pre = null; Node next = null; while (head ! = null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }

两个单链表相交的一系列问题