查找第N個節點  


難度級別 容易獎學金
經常問 ol石 土磚 亞馬遜 史詩系統 事實集 遠足 空氣質量 單排解決方案 高通公司 Snapdeal
花旗集團 鍊錶 鍊錶

問題陳述  

在“查找第N個節點”問題中,我們給出了一個 鍊錶 查找第n個節點。 程序應在第n個節點中打印數據值。 N是輸入整數索引。

  

3
1 2 3 4 5 6
3

途徑  

給定一個鍊錶,我們必須找到第n個節點。 我們有指向頭節點的指針。  我們可以創建一個指向頭節點的curr指針,並且還可以使用一個變量來計算在迭代鍊錶時所要節點的數量。 將count變量初始化為1。在每次迭代中,我們檢查count值是否等於n,如果等於n,則返回curr-> val。 否則,我們將移至下一個節點,並將count的值增加到1。

算法
  

  1. 取一個curr指針指向根節點,然後計算一個值為1的count變量
  2. 遍歷鏈接列表。
  3. 如果計數值等於n,則返回curr-> val
  4. 否則,將curr節點指向其下一個節點,並將count的值增加到1。

履行  

C ++程序查找第N個節點

#include<bits/stdc++.h>
using namespace std;

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        int val;
        ListNode(int a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(int val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    int nthNode(int n){
    	ListNode* curr = head;
    	int cnt=1;
    	while(curr){
    		if(cnt==n){
    			return curr->val;
    		}
    		curr = curr->next;
    		cnt++;
    	}
    	return -1;
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead(10);
  list->addAtHead(7);
  list->addAtHead(4);
  list->addAtHead(2);

    cout<<list->nthNode(3);
}

Java程序查找第N個節點

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead(10);
    obj.addAtHead(7);
    obj.addAtHead(4);
    System.out.println(obj.nthNode(3));
    
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          int val = 0;
          
          public Node(int val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(int val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
      public int nthNode(int n){
      	Node curr = head;
      	int cnt=1;
      	while(curr!=null){
      		if(cnt==n){
      			return curr.val;
      		}
      		curr = curr.next;
      		cnt=cnt+1;
      	}
      	return -1;
      }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}

複雜度分析  

時間複雜度

O(N) 哪裡 n 是給定的整數值。 在這裡,我們訪問n個需要線性時間的元素。

也可以看看
商店Leetcode解決方案中的最終價格具有特別折扣

空間複雜度

O(1) 因為我們在這裡不使用任何輔助空間。