我的刷题日记（9）

题目描述

输入一个链表，输出该链表中倒数第k个结点。

创建一个链表

function nodeList(x) { // 创建链表 this.val = x; this.next = null; } const arr1 = [1,2,3,4,5,6]; // 链表节点的值 function getNodeList(arr) { if(arr.length === 0){ return null; } const root = new nodeList(arr[0]); let p = root; for (let i = 1; i< arr.length;i++) { p.next = new nodeList(arr[i]); p = p.next; } return root; }

第一种方法思路：

找出一共有多少个节点倒数第k个是正数第几个？ function FindKthToTail(head, k) { if(head == null) { return null; } let p = head; let num = 0; while(p !== null) { p = p.next; num++; } if (k > num){ return null; } p = head; for(let i = 0;i<num -k;i++){ p = p.next; } return p; }

第二种方法思路：

定义两个指针让它们相差k个节点当前一个指针指向null当的时候说明前一个指针就指向了倒数第k个节点 function FindKthToTail(head, k) { if(head === null) { return null; } let p = head; let q = head; for (let i = 0 ;i<k;i++){ if(q === null){ // 当k大于总节点时 return null; } q = q.next; } while(q !== null) { q = q.next; p = p.next; } return p; }