剑指Offer之Java算法习题精讲链表专项训练

/**

  * Definition for singly-linked list.

  * 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; }

  * }

  */

class Solution {

     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

         ListNode a = new ListNode( 0 ),b = a;

         while (list1!= null &&list2!= null ){

             if (list1.val<=list2.val){

                 a.next = list1;

                 list1 = list1.next;

             } else {

                 a.next = list2;

                 list2 = list2.next;

             }

             a = a.next;

         }

         if (list1== null ){

             a.next = list2;

         }

         if (list2== null ){

             a.next = list1;

         }

         return b.next;

     }

}

/**

  * Definition for singly-linked list.

  * class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

public class Solution {

     public boolean hasCycle(ListNode head) {

         HashSet<ListNode> set = new HashSet<ListNode>();

         while (head!= null ){

             if (!set.add(head)){

                 return true ;

             }

             set.add(head);

             head = head.next;

         }

         return false ;

     }

}

/**

  * Definition for singly-linked list.

  * class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

public class Solution {

     public boolean hasCycle(ListNode head) {

         ListNode fast = head;

         ListNode slow = head;

         while (fast!= null ){

             if (fast.next== null ) return false ;

             slow = slow.next;

             fast = fast.next.next;

             if (fast==slow) return true ;

         }

         return false ;

     }

}

/**

  * Definition for singly-linked list.

  * class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

public class Solution {

     public ListNode detectCycle(ListNode head) {

         HashSet<ListNode> set = new HashSet<ListNode>();

         while (head!= null ){

             if (!set.add(head)){

                 return head;

             }

             set.add(head);

             head = head.next;

         }

         return null ;

     }

}

/**

  * Definition for singly-linked list.

  * class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

public class Solution {

     public ListNode detectCycle(ListNode head) {

         ListNode fast = head;

         ListNode slow = head;

         while (fast!= null ){

             if (fast.next== null ) return null ;

             slow = slow.next;

             fast = fast.next.next;

             if (slow == fast){

                 slow = head;

                 break ;

             }

         }

         while (fast!= null ){

             if (slow == fast){

                 return slow;

             }

             slow = slow.next;

             fast = fast.next;

         }

         return null ;

     }

}

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

public class Solution {

     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

         HashSet<ListNode> set = new HashSet<ListNode>();

         while (headA!= null ){

             set.add(headA);

             headA = headA.next;

         }

         while (headB!= null ){

             if (!set.add(headB)){

                 return headB;

             }

             set.add(headB);

             headB = headB.next;

         }

         return null ;

     }

}

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode(int x) {

  *         val = x;

  *         next = null;

  *     }

  * }

  */

public class Solution {

     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

         ListNode a = headA, b = headB;

         while (a != b){

             if (a == null ) a = headB;

             else a = a.next;

             if (b == null ) b = headA;

             else b = b.next;

         }

         return a;

     }

}

/**

  * Definition for singly-linked list.

  * 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; }

  * }

  */

class Solution {

     public ListNode removeNthFromEnd(ListNode head, int n) {

         ListNode node = new ListNode(- 1 );

         node.next = head;

         ListNode x = findFromEnd(node,n+ 1 );

         x.next = x.next.next;

         return node.next;

     }

     private ListNode findFromEnd(ListNode head, int k) {

         ListNode fast = head;

         ListNode slow = head;

         for ( int i = 0 ;i<k;i++){

             fast = fast.next;

         }

         while (fast!= null ){

             slow = slow.next;

             fast = fast.next;

         }

         return slow;

     }

}

/**

  * Definition for singly-linked list.

  * 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; }

  * }

  */

class Solution {

     public ListNode middleNode(ListNode head) {

         ListNode fast = head ;

         ListNode slow = head ;

         while (fast!= null ){

             if (fast.next == null ) return slow;

             slow = slow.next;

             fast = fast.next.next;

         }

         return slow;

     }

}