LeetCode Notes: Find K’th Node From the End of a Linked List

#leetcode

Question

Input a linked list, and output the k'th node from the end of the linked list. In order to conform to the habits of most people, this question starts counting from 1, that is, the end node of the linked list is the first node from the end.

For example, a linked list has 6 nodes. Starting from the head node, their values are 1, 2, 3, 4, 5, and 6. The third-to-last node in this linked list is the node with a value of 4.

Example:

Given a linked list: 1->2->3->4->5, and k = 2.

Return to the linked list 4->5.

Solution

Analysis:

  1. First define two pointers to point to the head
  2. Let one of the pointers go k steps first
  3. Let the two pointers go at the same time, and stop when the first pointer reaches the end of the linked list. At this time, the second pointer points to the position of n-k.

Code:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    //Define two pointers
    let first = head,second = head

    //The first pointer goes k steps first
    for(let i = 0; i < k; i++){
        first = first.next
    }

    //The two pointers go at the same time, and the end is from the first to the end, and then the second is at the position of n-k.
    while(first){
        first = first.next
        second = second.next
    }

    return second
};

Test:

//Define a 1->2->3->4->5 linked list
const linkedList = {
     head: {
         val: 1,
         next: {
             val: 2,
             next: {
                 val: 3,
                 next: {
                     val: 4,
                     next: {
                            val:5,
                             next:null
                         }
                     }
                 }
             }
         }
     }

//Find the penultimate item, it will output 4->5
getKthFromEnd(linkedList.head,2) //Output: 4->5

Reference

Comments