首页 > 代码库 > Leetcode: Remove Duplicates from Sorted List II 解题报告

Leetcode: Remove Duplicates from Sorted List II 解题报告

2024-08-10 05:10:27   216人阅读

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

技术分享

SOLUTION 1:

使用一个del标记来删除最后一个重复的字元。

技术分享
 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode deleteDuplicates(ListNode head) {14         if (head == null) {15             return null;16         }17         18         // record the head.19         ListNode dummy = new ListNode(0);20         dummy.next = head;21         22         ListNode cur = dummy;23         24         // to delete the last node in the list of duplications.25         boolean del = false;26         27         while (cur != null) {28             if (cur.next != null29                 && cur.next.next != null30                 && cur.next.val == cur.next.next.val) {31                 cur.next = cur.next.next;32                 del = true;33             } else {34                 if (del) {35                     cur.next = cur.next.next;36                     del = false;37                 } else {38                     cur = cur.next;39                 }40             }41         }42         43         return dummy.next;44     }45 }
View Code

SOLUTION 2:

使用一个pre, 一个cur来扫描，遇到重复的时候，使用for循环用cur跳过所有重复的元素。

技术分享
 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode deleteDuplicates(ListNode head) {14         if (head == null) {15             return null;16         }17         18         ListNode dummy = new ListNode(0);19         dummy.next = head;20         21         ListNode pre = dummy;22         ListNode cur = pre.next;23         24         while (cur != null && cur.next != null) {25             if (cur.val == cur.next.val) {26                 while (cur != null && cur.val == pre.next.val) {27                     cur = cur.next;28                 }29                 30                 // delete all the duplication.31                 pre.next = cur;32             } else {33                 cur = cur.next;34                 pre = pre.next;35             }36         }37         38         return dummy.next;39     }40 }
View Code

 

Leetcode: Remove Duplicates from Sorted List II 解题报告


联系
我们