java單連結清單練習題

新浪----查找單連結清單中的倒數第K個節點

思路分析：周遊整個連結清單，得到連結清單的總長度size，接着再次周遊（size-k）個即可。

public static Node findNode(Node head,int k){
 if(head.next==null){
       return null;
    }
    int size=getLength(head);//調用getLength()方法擷取連結清單長度
    if(k<=0||k>size){
       return null;
      }
      //定義輔助變量cur
      Node cur=head.next;
      for(int i=0;i<size-k;i++){
      cur=cur.next;
      }
      return cur;
      }
      //編寫周遊連結清單的方法，得到連結清單長度
      public static int getLength(Node head){
        if(head.next==null) return 0;
        int length=0;
        ListNode cur=head.next;
        while(cur!=null){
            length++;
            cur=cur.next;
        }
       return length;
    }
           

騰訊—單連結清單的反轉

思路分析：

思路:

1. 先定義一個節點 reverseHead = new HeroNode();
2. 周遊連結清單，每周遊一個節點，就将其取出，并放在新的連結清單reverseHead 的最前端.
3. 原來的連結清單的head.next = reverseHead.next;

public static void reversetList(Node head){
     if(head.next==null||head.next.next==null){
      return;
      }
      Node cur=head.next;
      Node next=null;
      Node reverseHead=new Node(0,"","");
      while(cur!=null){
      next=cur.next;//先暫時儲存目前節點的下個節點
      cur.next=reverseHead.next;//将cur接到新的連結清單上
      cur=next;//後移
      }
      head.next=reverseHead.next;
     }
           

百度–從尾到頭列印單連結清單

思路：将各個節點壓入到棧中，然後利用棧的先進後出的特點，将節點逐個出棧

public static reversePrint(Node head){
  if(head.next==null){
    retur;
  }
  
   Stack<Node>stack=new Stack<Node>();
   Node cur=head.next;
   while(cur!=null){
      stack.push(cur);
      cur=cur.next;
   }
   while(stack.size()>0){
   System.out.println(stack.pop());
   }
 }