如何分辨是这两种拓扑结构的哪一种呢？

如何分辨是这两种拓扑结构的哪一种呢？进入步骤3。

3．让链表1从loop1出发，因为loop1和之后的所有节点都在环上，所以将来一定能回到loop1。如果回到loop1之前并没有遇到loop2，说明两个链表的拓扑结构如图2-5所示，也就是不相交，直接返回null；如果回到loop1之前遇到了loop2，说明两个链表的拓扑结构如图2-6所示，也就是相交。因为loop1和loop2都在两条链表上，只不过loop1是离链表1较近的节点，loop2是离链表2较近的节点。所以，此时返回loop1或loop2都可以。

问题三的具体实现参看如下代码中的bothLoop方法。

public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { Node cur1 = null; Node cur2 = null; if (loop1 == loop2) { cur1 = head1; cur2 = head2; int n = 0; while (cur1 ! = loop1) { n++; cur1 = cur1.next; } while (cur2 ! = loop2) { n--; cur2 = cur2.next; } cur1 = n > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2 : head1; n = Math.abs(n); while (n ! = 0) { n--; cur1 = cur1.next; } while (cur1 ! = cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } else { cur1 = loop1.next; while (cur1 ! = loop1) { if (cur1 == loop2) { return loop1; } cur1 = cur1.next; } return null; } }

全部过程参看如下代码中的getIntersectNode方法，这也是整个题目的主方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node getIntersectNode(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); if (loop1 == null && loop2 == null) { return noLoop(head1, head2); } if (loop1 ! = null && loop2 ! = null) { return bothLoop(head1, loop1, head2, loop2); } return null; }

将单链表的每K 个节点之间逆序

【题目】

给定一个单链表的头节点head，实现一个调整单链表的函数，使得每K 个节点之间逆序，如果最后不够K 个节点一组，则不调整最后几个节点。

例如：

链表：1->2->3->4->5->6->7->8->null，K =3。

调整后为：3->2->1->6->5->4->7->8->null。其中7、8不调整，因为不够一组。

【难度】

尉　★★☆☆

【解答】

首先，如果K 的值小于2，不用进行任何调整。因为K<1没有意义，K==1时，代表每1个节点为1组进行逆序，原链表也没有任何变化。接下来介绍两种方法，如果链表长度为N ，方法一的时间复杂度为O (N )，额外空间复杂度为O (K )。方法二的时间复杂度为O (N )，额外空间复杂度为O (1)。本题考查面试者代码实现不出错的能力。

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

1．从左到右遍历链表，如果栈的大小不等于K ，就将节点不断压入栈中。

2．当栈的大小第一次到达K 时，说明第一次凑齐了K 个节点进行逆序，从栈中依次弹出这些节点，并根据弹出的顺序重新连接，这一组逆序完成后，需要记录一下新的头部，同时第一组的最后一个节点（原来是头节点）应该连接下一个节点。

例如：链表1->2->3->4->5->6->7->8->null，K = 3。第一组节点进入栈，从栈顶到栈底依次为3，2，1。逆序重连之后为3->2->1->…，然后节点1去连接节点4，链表变为3->2->1->4->5->6->7->8->null，之后从节点4开始不断处理K 个节点为一组的后续情况，也就是步骤3，并且需要记录节点3，因为链表的头部已经改变，整个过程结束后需要返回这个新的头节点，记为newHead。

3．步骤2之后，当栈的大小每次到达K 时，说明又凑齐了一组应该进行逆序的节点，从栈中依次弹出这些节点，并根据弹出的顺序重新连接。这一组逆序完成后，该组的第一个节点（原来是该组最后一个节点）应该被上一组的最后一个节点连接上，这一组的最后一个节点（原来是该组第一个节点）应该连接下一个节点。然后继续去凑下一组，直到链表都被遍历完。

例如：链表3->2->1->4->5->6->7->8->null，K = 3，第一组已经处理完。第二组从栈顶到栈底依次为6，5，4。逆序重连之后为6->5->4，然后节点6应该被节点1连接，节点4应该连接节点7，链表变为3->2->1->6->5->4->7->8->null。然后继续从节点7往下遍历。

4．最后应该返回newHead，作为链表新的头节点。

方法一的具体实现请参看如下代码中的reverseKNodes1方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node reverseKNodes1(Node head, int K) { if (K < 2) { return head; } Stackstack = new Stack(); Node newHead = head; Node cur = head; Node pre = null; Node next = null; while (cur ! = null) { next = cur.next; stack.push(cur); if (stack.size() == K) { pre = resign1(stack, pre, next); newHead = newHead == head ? cur : newHead; } cur = next; } return newHead; } public Node resign1(Stackstack, Node left, Node right) { Node cur = stack.pop(); if (left ! = null) { left.next = cur; } Node next = null; while (! stack.isEmpty()) { next = stack.pop(); cur.next = next; cur = next; } cur.next = right; return cur; }

方法二：不需要栈结构，在原链表中直接调整。

用变量记录每一组开始的第一个节点和最后一个节点，然后直接逆序调整，把这一组的节点都逆序。和方法一一样，同样需要注意第一组节点的特殊处理，以及之后的每个组在逆序重连之后，需要让该组的第一个节点（原来是最后一个节点）被之前组的最后一个节点连接上，将该组的最后一个节点（原来是第一个节点）连接下一个节点。

方法二的具体实现请参看如下代码中的reverseKNodes2方法。

public Node reverseKNodes2(Node head, int K) { if (K < 2) { return head; } Node cur = head; Node start = null; Node pre = null; Node next = null; int count = 1; while (cur ! = null) { next = cur.next; if (count == K) { start = pre == null ? head : pre.next; head = pre == null ? cur : head; resign2(pre, start, cur, next); pre = start; count = 0; } count++; cur = next; } return head; } public void resign2(Node left, Node start, Node end, Node right) { Node pre = start; Node cur = start.next; Node next = null; while (cur ! = right) { next = cur.next; cur.next = pre; pre = cur; cur = next; } if (left ! = null) { left.next = end; } start.next = right; }

删除无序单链表中值重复出现的节点

【题目】

给定一个无序单链表的头节点head，删除其中值重复出现的节点。

例如：1->2->3->3->4->4->2->1->1->null，删除值重复的节点之后为1->2->3->4->null。

请按以下要求实现两种方法。

方法1：如果链表长度为N ，时间复杂度达到O (N )。

方法2：额外空间复杂度为O (1)。

【难度】

士　★☆☆☆

【解答】

方法一：利用哈希表。时间复杂度为O (N )，额外空间复杂度为O (N )。

具体过程如下：

1．生成一个哈希表，因为头节点是不用删除的节点，所以首先将头节点的值放入哈希表。

2．从头节点的下一个节点开始往后遍历节点，假设当前遍历到cur节点，先检查cur的值是否在哈希表中，如果在，则说明cur节点的值是之前出现过的，就将cur节点删除，删除的方式是将最近一个没有被删除的节点pre连接到cur的下一个节点，即pre.next=cur.next。如果不在，将cur节点的值加入哈希表，同时令pre=cur，即更新最近一个没有被删除的节点。

方法一的具体实现请参看如下代码中的removeRep1方法。

public Node { public int value; public Node next; public Node(int data) { this.value = data; } } public void removeRep1(Node head) { if (head == null) { return; } HashSetset = new HashSet(); Node pre = head; Node cur = head.next; set.add(head.value); while (cur ! = null) { if (set.contains(cur.value)) { pre.next = cur.next; } else { set.add(cur.value); pre = cur; } cur = cur.next; } }

方法二：类似选择排序的过程，时间复杂度为O (N 2 )，额外空间复杂度为O (1)。

例如，链表1->2->3->3->4->4->2->1->1->null。

首先是头节点，节点值为1，往后检查所有值为1的节点，全部删除。链表变为：1->2->3->3->4->4->2->null。

然后是第二个节点，节点值为2，往后检查所有值为2的节点，全部删除。链表变为：1->2->3->3->4->4->null。

接着是第三个节点，节点值为3，往后检查所有值为3的节点，全部删除。链表变为：1->2->3->4->4->null。

最后是第四个节点，节点值为4，往后检查所有值为4的节点，全部删除。链表变为：1->2->3->4->null。

删除过程结束。