剑指 Offer 22. 链表中倒数第k个节点

方法一 双指针

 1 /**
 2  * Definition for singly-linked list.
 3  * function ListNode(val) {
 4  *     this.val = val;
 5  *     this.next = null;
 6  * }
 7  */
 8 /**
 9  * @param {ListNode} head
10  * @param {number} k
11  * @return {ListNode}
12  */
13 var getKthFromEnd = function(head, k) {
14     //双指针,第一个指针先走k步
15     let slow = head, fast = head;
16     while(k && fast) {
17         k--;
18         fast = fast.next;
19     }
20     while(fast) {
21         slow = slow.next;
22         fast = fast.next;
23     }
24     return slow;
25 };

 

方法二 数组

 1 /**
 2  * Definition for singly-linked list.
 3  * function ListNode(val) {
 4  *     this.val = val;
 5  *     this.next = null;
 6  * }
 7  */
 8 /**
 9  * @param {ListNode} head
10  * @param {number} k
11  * @return {ListNode}
12  */
13 var getKthFromEnd = function(head, k) {
14     let res = [];
15     while(head) {
16         res.push(head);
17         head = head.next;
18     }
19     return res[res.length - k];
20 };

 

上一篇:algorithm入门算法中的常见问题


下一篇:NC4 判断链表中是否有环