Topic describes
// If there are duplicate nodes in a sorted linked list, please delete the duplicate nodes in the linked list. // Duplicate nodes are not retained. Return the pointer to the head of the linked list. For example, linked list 1->2->3->3->4->4->5 // After processing is 1->2->5Copy the codeAnswer key
/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / double pointer / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / cow / / running time: 14 / ms/memory: 9916k public class Solution{ public ListNode deleteDuplication(ListNode pHead) { if (pHead == null || pHead.next == null) return pHead; ListNode dummy = new ListNode(-1); dummy.next = pHead; ListNode pre = dummy; ListNode cur = pHead; cur = cur.next; // Let the cur move to the right. We compare the pre. Next with the cur while (cur! Val == cur.val) {if (cur.next == null) {pre.next = null; // When you reach the end of the list, make the pre.next point to null break; } cur = cur.next; // Cur reaches the end of the repeating string if (pre-.next. Val! = cur.val) { pre.next = cur; // Set pre.next to cur = cur.next; }} else {pre = pre. Next; cur = cur.next; } } return dummy.next; // Do not return the pHead node}} // simplified version of the runtime: 14ms // memory: 9984k public class Solution{ public ListNode deleteDuplication(ListNode pHead) { if (pHead == null || pHead.next == null) return pHead; ListNode dummy = new ListNode(-1); dummy.next = pHead; ListNode pre = dummy; ListNode cur = pHead; while (cur ! = null) {// If (cur.next! = null && cur.next.val == cur.val) { while (cur.next ! = null && cur.next.val == cur.val) { cur = cur.next; // cur = cur.next; // cur = cur.next; pre.next = cur; } else {pre = pre. Next; cur = cur.next; } } return dummy.next; }}Copy the code/ / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / recursive method / / / / / / / / / / / / / / / / / / / / / / / / / / / / cow / / running time: 11 / ms/memory: 9948k public class Solution {public ListNode deleteDuplication(ListNode pHead) {// Before the start of the recursion, the pHead is the header. If pHead to traverse the nodes (pHead = = null | | pHead. Next = = null) {return pHead; } // 1. Before recursion, take the head node next and call it next // 2. // Next is pHead. Next, so it is pHead. Next refers to ListNode next = pHead. // start the while loop to find the repeating substring end // 2. If (pHead. Val == next-val) {// If (pHead. Val == next-val) {// If (pHead. Next (phead.Next-next) is not null while (next! = null && pHead.val == next.val) next = next.next; // Next moves right until traversing to the next node of the repeating substring. // Returns a recursive call of the deleteDuplication duplication. // After recursion and return, since next is referred to by phead.next, Return deleteDuplication(next); return deleteDuplication(next); } // If the header is not duplicated, else else {// Let pHead. Next point to the recursive call of the eleteDuplication duplication, enter pHead. The input pHead is actually referred to by the previous recursion phead. next, which is phead.next-next for the last recursion, and so on, essentially traversing the entire // list once. pHead.next = deleteDuplication(pHead.next); return pHead; }}}Copy the code