链表常见面试题
链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
function FindKthToTail(head, k) {
if (head == null) {
return false;
}
var currNode = head;
var arr = [];
while (currNode != null) {
arr.push(currNode);
currNode = currNode.next;
}
return arr[arr.length - k];
}合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
function Merge(pHead1, pHead2) {
if (pHead1 == null) {
return pHead2;
} else if (pHead2 == null) {
return pHead1;
}
var result = {};
if (pHead1.val < pHead2.val) {
result = pHead1;
result.next = Merge(pHead1.next, pHead2);
} else {
result = pHead2;
result.next = Merge(pHead1, pHead2.next);
}
return result;
}复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone(pHead) {
if (!pHead) {
return null;
}
var newHead = new RandomListNode(pHead.label);
newHead.random = pHead.random;
newHead.next = Clone(pHead.next);
return newHead;
}两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
var p1=pHead1;
var p2=pHead2;
while(p1!=p2){
p1=p1==null?pHead2:p1.next;
p2=p2==null?pHead1:p2.next;
}
return p1;
}链表中环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。
function EntryNodeOfLoop(pHead)
{
// write code here
if(pHead == null){
return 1;
}
if(pHead.next == null){
return null;
}
var fast = pHead;
var slow = pHead;
while(slow != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow) break;
}
var p1 = slow;
var p2 = pHead;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
function deleteDuplication(pHead) {
var newHead = new ListNode('head');
newHead.next = pHead;
var pHead = newHead;
var qHead = pHead.next;
while (qHead) {
while ((qHead.next != null) && (qHead.val == qHead.next.val)) {
qHead = qHead.next;
}
//没移动
if (pHead.next == qHead) {
pHead = qHead;
qHead = qHead.next;
}
//移动了
else {
qHead = qHead.next;
pHead.next = qHead;
}
}
return newHead.next;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录