如果链表长度为N ，时间复杂度达到O (N )，额外空间复杂度达到O (1)

全部过程请参看如下代码中的reversePart方法。

public Node reversePart(Node head, int from, int to) { int len = 0; Node node1 = head; Node fPre = null; Node tPos = null; while (node1 ! = null) { len++; fPre = len == from - 1 ? node1 : fPre; tPos = len == to + 1 ? node1 : tPos; node1 = node1.next; } if (from > to || from < 1 || to > len) { return head; } node1 = fPre == null ? head : fPre.next; Node node2 = node1.next; node1.next = tPos; Node next = null; while (node2 ! = tPos) { next = node2.next; node2.next = node1; node1 = node2; node2 = next; } if (fPre ! = null) { fPre.next = node1; return head; } return node1; }

环形单链表的约瑟夫问题

【题目】

据说著名犹太历史学家Josephus有过以下故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，报数到3的人就自杀，然后再由下一个人重新报1，报数到3的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表描述该结构并呈现整个自杀过程。

输入：一个环形单向链表的头节点head和报数的值m 。

返回：最后生存下来的节点，且这个节点自己组成环形单向链表，其他节点都删掉。

进阶：

如果链表节点数为N ，想在时间复杂度为O (N )时完成原问题的要求，该怎么实现？

【难度】

原问题：士　★☆☆☆

进阶：校　★★★☆

【解答】

先来看看普通解法是如何实现的，其实非常简单，方法如下：

1．如果链表为空或者链表节点数为1，或者m 的值小于1，则不用调整就直接返回。

2．在环形链表中遍历每个节点，不断转圈，不断让每个节点报数。

3．当报数到达m 时，就删除当前报数的节点。

4．删除节点后，别忘了还要把剩下的节点继续连成环状，继续转圈报数，继续删除。

5．不停地删除，直到环形链表中只剩一个节点，过程结束。

普通的解法就像题目描述的过程一样，具体实现请参看如下代码中的josephusKill1方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node josephusKill1(Node head, int m) { if (head == null || head.next == head || m < 1) { return head; } Node last = head; while (last.next ! = head) { last = last.next; } int count = 0; while (head ! = last) { if (++count == m) { last.next = head.next; count = 0; } else { last = last.next; } head = last.next; } return head; }

普通的解法在实现上不难，就是考查面试者基本的代码实现技巧，做到不出错即可。很明显的是，每删除掉一个节点，都需要遍历m 次，一共需要删除的节点数为n -1，所以普通解法的时间复杂度为O (n ×m )，这明显是不符合进阶要求的。

下面介绍进阶的解法。原问题之所以花费的时间多，是因为我们一开始不知道到底哪一个节点最后会活下来。所以依靠不断地删除来淘汰节点，当只剩下一个节点的时候，才知道是这个节点。如果不通过一直删除方式，有没有办法直接确定最后活下来的节点是哪一个呢？这就是进阶解法的实质。

举个例子，环形链表为：1->2->3->4->5->1，这个链表节点数为n =5，m =3。

通过不断删除的方式，最后节点4会活下来。但我们可以不用一直删除的方式，而是用进阶的方法，根据n 与m 的值，直接算出是第4个节点最终会活下来，接下来找到节点4即可。

那到底怎么直接算出来呢？首先，如果环形链表节点数为n ，我们做如下定义：从这个环形链表的头节点开始编号，头节点编号为1，头节点的下一个节点编号为2，……，最后一个节点编号为n 。然后考虑如下问题：

最后只剩下一个节点，这个幸存节点在只由自己组成的环中编号为1，记为Num(1) = 1；

在由两个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是Num(2)；

……

在由i -1个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是Num(i-1)；

在由i 个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是Num(i)；

……

在由n 个节点组成的环中，这个幸存节点的编号是多少呢？假设编号是Num(n)。

我们已经知道Num(1) = 1，如果再确定Num(i-1)和Num(i)到底是什么关系，就可以通过递归过程求出Num(n)。Num(i-1)和Num(i)的关系分析如下：

1．假设现在圈中一共有i 个节点，从头节点开始报数，报1的是编号1的节点，报2的是编号2的节点，假设报A的是编号B的节点，则A和B的对应关系如下。

A B 1 1

2 2 ... ... i i i +1 1 i +2 2 ... ... 2i i 2i +1 1 2i +2 2 … …

举个例子，环形链表有3个节点，报1的是编号1，报2的是编号2，报3的是编号3，报4的是编号1，报5的是编号2，报6的是编号3，报7的是编号1，报8的是编号2，报9的是编号3，报10的是编号1……

如上A和B的关系用数学表达式来表示可以写成：B=(A-1)%i+1。这个表达式不一定是唯一的，读者只要能写出准确概括A和B关系的式子就可以。总之，要找到报数（A）和编号节点（B）之间的关系。

2．如果编号为s的节点被删除，环的节点数自然从i 变成了i -1。那么原来在大小为i 的环中，每个节点的编号会发生什么变化呢？变化如下：

环大小为i的每个节点编号　　　删掉编号s的节点后，环大小为i-1的每个节点编号 ... … s-2 i -2 s-1 i -1 s —（无编号是因为被删掉了） s+1 1 s+2 2 ... …

新的环只有i -1个节点，因为有一个节点已经删掉。编号为s的节点往后，编号为s+1、s+2、s+3的节点就变成了新环中的编号为1、2、3的节点；编号为s的节点的前一个节点，也就是编号s-1的节点，就成了新环中的最后一个节点，也就是编号为i -1的节点。

假设环大小为i 的节点编号记为old，环大小为i -1的每个节点编号记为new，则old与new关系的数学表达式为：old=(new+s-1)%i+1。表达式同样不止一种，写出一种满足的即可。

3．因为每次都是报数到m 的节点被杀，所以根据步骤1的表达式B=(A-1)%i+1，A=m。被杀的节点编号为(m-1)%i+1，即s=(m-1)%i+1，带入到步骤2的表达式old=(new+s-1)%i+1中，经过化简为old=(new+m-1)%i+1。至此，我们终于得到了Num(i-1)—new和Num(i)—old的关系，且这个关系只和m 与i 的值有关。

整个进阶解法的过程总结为：

1．遍历链表，求链表的节点个数记为n ，时间复杂度为O (N )。

2．根据n 和m 的值，还有上文分析的Num(i-1)和Num(i)的关系，递归求生存节点的编号；这一步的具体过程请参看如下代码中的getLive方法，getLive方法为单决策的递归函数，且递归为N 层，所以时间复杂度为O (N )。

3．最后根据生存节点的编号，遍历链表找到该节点，时间复杂度为O (N )。

4．整个过程结束，总的时间复杂度为O (N )。

进阶解法的全部过程请参看如下代码中的josephusKill2方法。

public Node josephusKill2(Node head, int m) { if (head == null || head.next == head || m < 1) { return head; } Node cur = head.next; int tmp = 1; // tmp -> list size while (cur ! = head) { tmp++; cur = cur.next; } tmp = getLive(tmp, m); // tmp -> service node position while (--tmp ! = 0) { head = head.next; } head.next = head; return head; } public int getLive(int i, int m) { if (i == 1) { return 1; } return (getLive(i - 1, m) + m - 1) % i + 1; }

判断一个链表是否为回文结构

【题目】

给定一个链表的头节点head，请判断该链表是否为回文结构。

例如：

1->2->1，返回true。

1->2->2->1，返回true。

15->6->15，返回true。

1->2->3，返回false。

进阶：

如果链表长度为N ，时间复杂度达到O (N )，额外空间复杂度达到O (1)。

【难度】

普通解法　士　★☆☆☆

进阶解法　尉　★★☆☆

【解答】

方法一：

方法一是最容易实现的方法，利用栈结构即可。从左到右遍历链表，遍历的过程中把每个节点依次压入栈中。因为栈是先进后出的，所以在遍历完成后，从栈顶到栈底的节点值出现顺序会与原链表从左到右的值出现顺序反过来。那么，如果一个链表是回文结构，逆序之后，值出现的次序还是一样的，如果不是回文结构，顺序就肯定对不上。

例如：

链表1->2->3->4，从左到右依次压栈之后，从栈顶到栈底的节点值顺序为4，3，2，1。两者顺序对不上，所以这个链表不是回文结构。

链表1->2->2->1，从左到右依次压栈之后，从栈顶到栈底的节点值顺序为1，2，2，1。两者顺序一样，所以这个链表是回文结构。

方法一需要一个额外的栈结构，并且需要把所有的节点都压入栈中，所以这个额外的栈结构需要O (N )的空间。具体过程请参看如下代码中的isPalindrome1方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public boolean isPalindrome1(Node head) { Stackstack = new Stack(); Node cur = head; while (cur ! = null) { stack.push(cur); cur = cur.next; } while (head ! = null) { if (head.value ! = stack.pop().value) { return false; } head = head.next; } return true; }

方法二：

方法二对方法一进行了优化，虽然也是利用栈结构，但其实并不需要将所有的节点都压入栈中，只用压入一半的节点即可。首先假设链表的长度为N ，如果N 是偶数，前N /2的节点叫作左半区，后N /2的节点叫作右半区。如果N 是奇数，忽略处于最中间的节点，还是前N /2的节点叫作左半区，后N /2的节点叫作右半区。

例如：

链表1->2->2->1，左半区为：1，2；右半区为：2，1。

链表1->2->3->2->1，左半区为：1，2；右半区为：2，1。

方法二就是把整个链表的右半部分压入栈中，压入完成后，再检查栈顶到栈底值出现的顺序是否和链表左半部分的值相对应。

例如：

链表1->2->2->1，链表的右半部分压入栈中后，从栈顶到栈底为1，2。链表的左半部分也是1，2。所以这个链表是回文结构。

链表1->2->3->2->1，链表的右半部分压入栈中后，从栈顶到栈底为1，2。链表的左半部分也是1，2。所以这个链表是回文结构。

链表1->2->3->3->1，链表的右半部分压入栈中后，从栈顶到栈底为1，3。链表的左半部分也是1，2。所以这个链表不是回文结构。

方法二可以直观地理解为将链表的右半部分“折过去”，然后让它和左半部分比较，如图2-1所示。

图2-1

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

public boolean isPalindrome2(Node head) { if (head == null || head.next == null) { return true; } Node right = head.next; Node cur = head; while (cur.next ! = null && cur.next.next ! = null) { right = right.next; cur = cur.next.next; } Stackstack = new Stack(); while (right ! = null) { stack.push(right); right = right.next; } while (! stack.isEmpty()) { if (head.value ! = stack.pop().value) { return false; } head = head.next; } return true; }

方法三：

方法三不需要栈和其他数据结构，只用有限几个变量，其额外空间复杂度为O (1)，就可以在时间复杂度为O (N )内完成所有的过程，也就是满足进阶的要求。具体过程如下：

1．首先改变链表右半区的结构，使整个右半区反转，最后指向中间节点。

例如：

链表1->2->3->2->1，通过这一步将其调整之后的结构如图2-2所示。

图2-2

链表1->2->3->3->2->1，将其调整之后的结构如图2-3所示。

图2-3

我们将左半区的第一个节点（也就是原链表的头节点）记为leftStart，右半区反转之后最右边的节点（也就是原链表的最后一个节点）记为rightStart。

2.leftStart和rightStart同时向中间点移动，移动每一步都比较leftStart和rightStart节点的值，看是否一样。如果都一样，说明链表为回文结构，否则不是回文结构。

3．不管最后返回的是true还是false，在返回前都应该把链表恢复成原来的样子。

4．链表恢复成原来的结构之后，返回检查结果。

粗看起来，虽然方法三的整个过程也没有多少难度，但要想用有限几个变量完成以上所有的操作，在实现上还是比较考查代码实现能力的。方法三的全部过程请参看如下代码中的isPalindrome3方法，该方法只申请了三个Node类型的变量。

public boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = head; Node n2 = head; while (n2.next ! = null && n2.next.next ! = null) { // 查找中间节点 n1 = n1.next; // n1 -> 中部 n2 = n2.next.next; // n2 -> 结尾 } n2 = n1.next; // n2 -> 右部分第一个节点 n1.next = null; // mid.next -> null Node n3 = null; while (n2 ! = null) { // 右半区反转 n3 = n2.next; // n3 -> 保存下一个节点 n2.next = n1; // 下一个反转节点 n1 = n2; // n1 移动 n2 = n3; // n2 移动 } n3 = n1; // n3 -> 保存最后一个节点 n2 = head; // n2 -> 左边第一个节点 boolean res = true; while (n1 ! = null && n2 ! = null) { // 检查回文 if (n1.value ! = n2.value) { res = false; break; } n1 = n1.next; // 从左到中部 n2 = n2.next; // 从右到中部 } n1 = n3.next; n3.next = null; while (n1 ! = null) { // 恢复列表 n2 = n1.next; n1.next = n3; n3 = n1; n1 = n2; } return res; }