第二章：链表问题（二）

环形单链表的约瑟夫问题

【题目】

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

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

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

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

【难度】

原问题  士 ★☆☆☆

进阶问题 校 ★★★☆

【解答】

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

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

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

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

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

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

	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)了。下面是求解的过程。

首先来认识一个非常简单的函数f(x)=x%i的图像，如图2-1所示。

报数和编号之间的关系

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

报数  编号

1                                                                   1

...                           ...

i i

i+1          1

...                   ...

2i i

2i+1             1

…                   …

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

报数和编号的关系图如图2-2所示。

可以发现报数和编号的关系图，就是f(x)=x%i函数图像先向右平移一个单位，再向上平移一个单位得到的，根据左加右减、上加下减的原理可以得到：编号=（报数-1）%i+1

下面来解决杀死节点之前的老编号和杀死节点后的新编号的关系。

如果编号为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的节点。

这样的分析还不足以看出是什么关系，我们来举个例子。如果杀死之前有9个节点，杀死之后有8个节点，被杀死的是编号4，新老编号对应关系如下：

老编号 ：1  2  3  4  5  6  7  8  9

新编号 ：6  7  8  无1  2  3  4  5

画出对应关系图如图2-3所示。

假设被杀节点的编号为s，图2-3就是图2-4中的一段而已。

图2-4中实线的部分就是新老编号的对应关系。我们看一下之前求出的函数，编号=（报数-1）%i+1的图像，该图像往左平移s个单位，就是新老编号的对应关系的图像。所以新老编号的对应关系函数为：老编号=（新编号+s-1）%i+1

s的含义是被杀的节点编号，但是被杀节点的编号如何确定呢？因为在长度为i的环中，被杀死的总是报数到m的节点，又有：编号=（报数-1）%i+1，所以s=(m-1)%i+1。再将s的值带入，老编号=（新编号+(m-1)%i）%i+1。

我们可以假设m-1=k*i+b（K≥0），就是说把m-1认为是k个i再加一个余数b。那么，(新编号+(m-1)%i)%i+1 = (新编号+b)%i+1。

再看这个式子：（新编号+m-1）%i+1。如果把m-1=k´i+b带入，（新编号+m-1）%i+1=（新编号+b）%i+1。所以原来的等式可以进一步化简为，老编号=（新编号+m-1）%i+1。

至此，已经求出了杀死一个节点前后编号的变化函数，所以整个解法的过程总结为：

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

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

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

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

	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。两者顺序一样，所以这个链表是回文结构。

	public class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public boolean isPalindrome1(Node head) {
		Stack<Node> stack = new Stack<Node>();
		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-5所示。

	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;
		}
		Stack<Node> stack = new Stack<Node>();
		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-6所示。

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

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

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

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

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

	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;
	}