最強單連結串列合集（二）相關題解

一、計算連結串列中節點個數

  /**
    * @param head  不計算頭結點
    * @return count 連結串列中的結點個數
    */
 public static int getLength(Node head) {
  if(head.next==null) {
      return 0;
  }
  Node temp =head.next;
  int count=0;
  while(temp!=null){
      count++;
      temp=temp.next;
  }
  return count;
 }

二、查詢倒數第k個節點

    /**
     * @param k
     * @param head
     * @return 返回倒數第k個節點
     */
 public static Node findIndexNode(int k,Node head){
      if(head.next == null){
          System.out.println("連結串列為空");
          return:
      }
      int size = getLength(head);
      int num = size-k; //要遍歷的次數
      Node temp = head.next;
     for(int i =0;i<num;i++){
         temp=temp.next;
     }
     return temp;
 }

三、單連結串列的反轉

public static void reverse(Node head) {
     if(head.next ==null||head.next.next==null){
         return;
     }
     Node cur=head.next;
     Node next=null;
     Node newList=new Node(0);
     while(cur!=null){
         next=cur.next; //next儲存下一節點
         cur.next =newList.next; //將cur的下一節點加入新連結串列的最前端
         newList.next=cur; //當前節點連結到新連結串列
         cur=next; //cur指向下一節點
     }
     head.next=newList.next;
}

四、從尾到頭列印單連結串列

 public static void reversePrint(Node head) {
        Stack<Node> stack = new Stack();
        Node temp = head.next;
        //將所有節點壓入棧
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        //當棧不為空時，彈棧並顯示
        while (!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }

五、刪除排序連結串列中的重複元素（不帶頭結點）

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
public ListNode deleteDuplicates(ListNode head) {
    if(head == null){
        return null;
    }
    ListNode node = head;
    while(node!=null&&node.next!=null){
        if(node.val==node.next.val){
            node.next= node.next.next;
        }
        else{
            node=node.next;
        }
    }
    return head;
    }

六、判斷連結串列是否有環（不帶頭結點）

快指標比慢指標每次走兩步

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
   public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}    

七、返回環形連結串列中的第一個結點（不帶頭結點）

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
    public ListNode detectCycle(ListNode head) {
        if( head == null || head.next ==null){
            return null;
        }
        ListNode slow =head;
        ListNode fast= head;
        while(fast!=null){
          slow = slow.next;
          if(fast.next != null){
              fast=fast.next.next;
          }else{
              return null;
          }
          if(fast == slow){
              ListNode temp = head;
              while(temp!=slow){
                  temp=temp.next;
                  slow=slow.next;
              }
              return temp;
          }
        }
        return null;

八、兩兩交換連結串列中的結點（不帶頭結點）

 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 public ListNode swapPairs(ListNode head) {
        ListNode pre =new ListNode(0);
        pre.next =head;
        ListNode temp = pre;
        while(temp.next!=null&&temp.next.next!=null){
            ListNode node1 = temp.next;
            ListNode node2=temp.next.next;  
            temp.next= node2;              //交換前後結點
            node1.next =node2.next;
            node2.next =node1;
            temp=node1;
        }
        return pre.next;
    }