LeetCode【83. 删除排序链表中的重复元素】

迈不过友情╰ 2022-05-09 02:33 168阅读 0赞

### 题目描述 ###

> 给定一个 排序链表，删除所有重复的元素，使得每个元素之出现一次。

**示例 \* 1**

*  ***输入***: 1->1->2
 *  ***输出***: 1->2

**示例 \* 2**

*  ***输入***: 1->1->2->2->3->3
 *  ***输出***: 1->2->3

**思路 \* 1**  
初始化一个ListNode变量 cur 使其保留原来链表的初始位置，然后使用 h e a d head head对其链表进行遍历，遍历时删除相邻的相等的元素，同时注意一下条件语句，需要 h e a d ! = n u l l head != null head!=null 和  h e a d . n e x t ! = n u l l head.next != null head.next!=null的顺序。  
**代码 \* 1**

class Solution { public ListNode deleteDuplicates(ListNode head){ ListNode cur = new ListNode(-1); cur.next = head; while(head != null && head.next != null) { if(head.next.val == head.val) { head.next = head.next.next; }else { head = head.next; } } return cur.next; } }

**复杂度分析**

*  **时间复杂度** :  O ( N ) O(N) O(N)
 *  **空间复杂度** :  O ( 1 ) O(1) O(1)

**思路 \* 2**：  
将上面的代码改为递归的形式。  
**代码 \* 2**

class Solution { public ListNode deleteDuplicates(ListNode head){ if(head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); return head.next.val == head.val ? head.next : head; } }

**复杂度分析**

*  **时间复杂度** :  O ( N ) O(N) O(N)
 *  **空间复杂度** :  O ( N ) O(N) O(N)

**完整代码**

package leetcode83; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by 张超帅 on 2018/9/29. */ class ListNode { int val; ListNode next; ListNode (int val) { this.val = val; } } class Solution { public ListNode deleteDuplicates(ListNode head){ if(head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); return head.next.val == head.val ? head.next : head; } } public class leetcode83 { public static int[] stringToArrays(String input) { input = input.trim(); input = input.substring(1, input.length() - 1); if(input == null) { return new int[0]; } String[] parts = input.split(","); int[] result = new int[parts.length]; for(int i = 0; i < parts.length; i ++) { String part = parts[i].trim(); result[i] = Integer.parseInt(part); } return result; } public static ListNode stringToListnode(String input) { int[] nodeValues = stringToArrays(input); ListNode dummpy = new ListNode(-1); ListNode cur = dummpy; for(int value : nodeValues) { cur.next = new ListNode(value); cur = cur.next; } return dummpy.next; } public static String listnodeToString(ListNode ret){ if(ret == null) { return "[]"; } String s = ""; while(ret != null) { s = s + ret.val + ", "; ret = ret.next; } return "[" + s.substring(0, s.length() - 2) + "]"; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = in.readLine()) != null) { ListNode head = stringToListnode(line); ListNode ret = new Solution().deleteDuplicates(head); String out = listnodeToString(ret); System.out.println(out); } } }