【Java算法】链表合并去重算法

清疚 2024-03-27 08:46 83阅读 0赞

#### 文章目录 ####

*  删除有序列表中的重复元素
 *  有序链表合并

## 删除有序列表中的重复元素 ##

既然我们要删除一个有序的链表中的重复元素，那么我们可以这样子想。  
如果这个元素与他的下一个元素重复了，那么我们就让这个元素的下一个元素覆盖这个元素即可，这样子就消除了一个重复的元素，重复这样子，就能做到把数组中的重复元素都去除。而如果不是重复的，那么我们直接让遍历指针下移即可。

//  * 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 deleteDuplicates(ListNode head) {
        
    //         ListNode headResult = head;
    //         ListNode temp = head;
    //         boolean flag = false;
    //         while (head!=null) {
        
    //             flag = false;
    //             int cur = temp.val;
    //             for (; temp!=null&&temp.val == cur; temp = temp.next) {
        
    //                 flag = true;
    //             }
    //             if (flag) {
        
    //                 head.next = temp;
    //             }
    //             head = head.next;
    //         }
    //         return headResult;
    //     }
    // }
    class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            if (head == null) {
        
                return head;
            }
    
            ListNode cur = head;
            while (cur.next != null) {
        
                if (cur.val == cur.next.val) {
        
                    cur.next = cur.next.next;
                } else {
        
                    cur = cur.next;
                }
            }
    
            return head;
        }
    }

## 有序链表合并 ##

由于链表有序，因此我们可以定义一个头节点，之后将这两个链表的元素直接添加到这个头节点中即可。  
如果链表1的元素大，那么就向头节点添加链表2的节点，并且让链表2节点后移一位。  
之后，当某一条链表的元素都被添加到头节点后，会存在一条链表的元素还没有被添加到头节点，但是由于链表有序，因此这个剩下的元素，一定都比头节点中的元素大于或者等于，因此直接插入到头节点中即可。

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 mergeTwoLists(ListNode l1, ListNode l2) {
                ListNode prehead = new ListNode(-1);
    
                ListNode prev = prehead;
                while (l1 != null && l2 != null) {
                    if (l1.val <= l2.val) {
                        prev.next = l1;
                        l1 = l1.next;
                    } else {
                        prev.next = l2;
                        l2 = l2.next;
                    }
                    prev = prev.next;
                }
    
                // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
                prev.next = l1 == null ? l2 : l1;
    
                return prehead.next;
            }
    }