第6题：链表中倒数最后k个结点
-
题目描述
输入一个长度为n的链表，设链表中的元素的值为\(a_i\)，返回该链表中的第k个结点。
如果该链表长度小于\(k\)，请返回一个长度为0的链表 -
思路
双指针- step1: 准备一个快指针，从链表头开始，在链表上先走k步。
- step2: 准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一致都是k。
- step3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
特点：双指针的初始位置、快慢。
-
答案
class Solution {
public:
ListNode* FindKthToTail(ListNode* pHead, int k) {
ListNode* fast = pHead;
ListNode* slow = pHead;
//快指针先行k步
for(int i = 0; i < k; i++){
if(fast != NULL)
fast = fast->next;
//达不到k步说明链表过短，没有倒数k
else
return slow = NULL;
}
//快慢指针同步，快指针先到底，慢指针指向倒数第k个
while(fast != NULL){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
第7题：复杂链表的复制
- 题目描述
输入一个复杂链表（每个结点有结点值，以及两个指针，一个指向下一个结点，另一个特殊指针random指向一个随机结点），请对此链表进行深拷贝。（注意：输出结果中请不要返回参数中的结点引用，否则判题程序会直接返回空）。下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。 - 思路
组合链表（双指针）
正常链表的复制，从头到尾遍历链表，对于每个结点创建新的结点，赋值，并将其连接好就可以了。这道题的不同之处在于我们还要将随机指针连接好，我们创建结点的时候，有可能这个结点创建了，但是它的随机指针指向的结点没有创建，因此创建的时候只能连接指向后面的指针，无法连接随机指针。
等链表连接好了，再连接随机指针的话，我们又难以找到这个指针指向的位置，因为链表不支持随机访问。但是吧，我们待拷贝的链表可以随机指针访问节点，那么我们不如将拷贝后的每个结点插入到原始链表相应结点之后，这样连接random指针的时候，原始链表random指针后一个元素就是原始链表要找的随机节点，而该节点后一个就是它拷贝出来的新节点，则就可以连上了。- step1：遍历链表，对每个结点新建一个拷贝结点，并插入到该节点之后。
- step2：使用双指针再次遍历链表，两个指针每次移动两步，一个指针遍历原始节点，一个指针遍历拷贝节点，拷贝节点的随机指针跟随原始节点，指向原始节点随机指针的下一位。
- step3：再次使用双指针遍历链表，每次越过一位后相连，即拆分成两个链表。
- 答案
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
//空节点直接返回
if(pHead == null)
return pHead;
//添加一个头部节点
RandomListNode cur = pHead;
//遍历原始链表，开始复制
while(cur != null){
//拷贝节点
RandomListNode clone = new RandomListNode(cur.label);
//将新节点插入到被拷贝的节点后
clone.next = cur.next;
cur.next = clone;
cur = clone.next;
}
cur = pHead;
RandomListNode clone = pHead.next;
RandomListNode res = pHead.next;
//连接新链表的random节点
while(cur != null){
//跟随前一个连接random
if(cur.random == null)
clone.random = null;
else
//后一个节点才是拷贝的
clone.random = cur.random.next;
//cur.next必定不为空
cur = cur.next.next;
//检查末尾节点
if(clone.next != null)
clone = clone.next.next;
}
cur = pHead;
clone = pHead.next;
//拆分两个链表
while(cur != null){
//cur.next必定不为空
cur.next = cur.next.next;
cur = cur.next;
//检查末尾节点
if(clone.next != null)
clone.next = clone.next.next;
clone = clone.next;
}
return res;
}
}