剑指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;
   }
}

来源：https://blog.csdn.net/wai_58934/article/details/122991115