leetcode 82删除排序链表中的重复元素

妖狐艹你老母 2023-06-21 14:29 51阅读 0赞

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5  
输出: 1->2->5  
示例 2:

输入: 1->1->1->2->3  
输出: 2->3  
在真实的面试中遇到过

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    
    思路：递归
    class Solution {
        
        int val = -100;
        public ListNode deleteDuplicates(ListNode head) {
        
              if (head == null) return null;
    
            ListNode node = deleteDuplicates(head.next);
            head.next = null;
            if (node == null)
            {
        
                if (head.val == val) {
        
                    return null;
                } else 
                    return head;
            }
            if (node.val == head.val) {
        
                val = head.val;
                return node.next;
            }
            if (head.val == val) {
        
                val = head.val;
                return node;
            }
            head.next = node;
            return head;
        }
    }

2.递归

public ListNode deleteDuplicates(ListNode head) {
        
              if (head == null || head.next == null) return head;
    
              if (head.val == head.next.val) {
        
                ListNode nenode = head.next;
                 while (nenode.next != null && nenode.val == nenode.next.val) {
        
                     nenode = nenode.next;
                 } 
                 return deleteDuplicates(nenode.next);   
    
              }  else {
        
                  head.next = deleteDuplicates(head.next);
              }
                return head;
        }

迭代

public ListNode deleteDuplicates(ListNode head) {
        
            if (head == null || head.next == null) return head;
            
            ListNode root = new ListNode(-100);
            root.next = head;
            ListNode cur = head;
            ListNode pre = root;
    
            while (cur != null) {
        
                
                if (cur.next != null && cur.val == cur.next.val) {
        
                while (cur.next != null && cur.val == cur.next.val) {
        
                    cur = cur.next;
                }
    
                pre.next = cur.next;
                cur = cur.next;
                } else {
        
                cur = cur.next;
                pre = pre.next;
                }
    
            }
    
            return root.next;
        }