【算法链表】单链表算法总结

合并两个有序链表

合并两个有序链表

**
 * 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 dummy = new ListNode(-1); 
        ListNode p = dummy;
        ListNode p1 = list1;
        ListNode p2 = list2;

        //循环合并期间，任何一个链表到尾部了，循环结束。
        while(p1 != null && p2 != null){ 
            if(p1.val > p2.val){
                p.next = p2;
                p2 = p2.next;
            }else{
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        //运行到此处，循环结束，剩余的一个链表部分，直接挂在新链表尾部
        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
        //从虚拟头结点之后开始算新的链表  
        return dummy.next;
    }
}

合并k个升序链表

合并ke个升序链表

/**
 * 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 mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;

        //虚拟头结点
        ListNode dummy = new ListNode();
        ListNode p = dummy;

        //创建一个优先级队列
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b) -> (a.val - b.val));

        //将k个结点存储到队列中
        for(ListNode head : lists){
            if(head != null){
                pq.add(head);
            }
        }
        //队列不为空的时候，将队列的数据取出，塞到新队列后面之后，将下一个非空结点塞到新的链表中
        while(!pq.isEmpty()){
            ListNode minNode =  pq.poll();
            p.next = minNode;
            if(minNode.next != null){
                pq.add(minNode.next);
            }
            p = p.next;
        }
        return dummy.next;
    }
  }

链表的中间结点

链表中间结点

/**
 * 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 slow,fast;
        slow = fast = head;
        //慢指针一次跳1步，快指针，一次跳2步。等快指针走到边界的时候，慢指针刚好走到中点
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

环形链表（简单）

环形链表

/**
 * 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 slow ,fast;
        slow = fast = head;
        //快慢指针，快慢指针相交，即为有环
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

环形链表II

环形链表II

/**
 * 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 slow ,fast;
        slow = fast = head;
        //快慢指针，快慢指针相交，即为有环
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                break;
            }
        }

        if(fast == null || fast.next == null){
            return null;
        }

        slow = head;

        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

删除链表倒数第N 个节点

删除链表倒数第N个节点

/**
 * 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 dummy = new ListNode(-1);
        dummy.next = head;
        //删除倒数第k个结点，需要找到倒数第k+1个结点，然后将这个结点的next指向next的next结点。
        ListNode end = findFromEnd(dummy, n + 1);
        end.next = end.next.next;
        return dummy.next;
    }

    public ListNode findFromEnd(ListNode head, int k){
        //双指针，先让p1指针走k步
        ListNode p1 = head;
        for(int i = 0; i< k; i++){
            p1 = p1.next;
        }
        ListNode p2 = head;
        //p1,p2指针同时走，先走的p1,需要走n-k步，到链表尾部，p2走n-k步，刚好到倒数第k个结点。
        while(p1 != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}

相交链表

相交链表

/**
 * 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 p1 = headA;
        ListNode p2 = headB;
        //两个指针分别从A ，B 开始循环遍历，遍历结束开始遍历另外一张链表，两个指针相等时退出。
        while(p1 != p2){
            if(p1==null){
                p1 = headB;
            }else{
                p1 = p1.next;
            }
            if(p2 == null){
                p2 = headA;
            }else{
                p2 = p2.next;
            }
        }
        return p1;
    }
}