Topic describes

This is “JZ 56 Delete Duplicated Node in Linked List” on “Niuke.com”, difficulty is “Difficult”.

Tag: “sword point Offer”, “linked list”, “single linked list”

In a sorted list, there are duplicate nodes, delete the duplicate nodes in the list, duplicate nodes are not reserved, return the list head pointer.

For example, linked list 1->, 2->, 3->, 3->, 4->, 4->, 1->, 2->, 5

Example 1:

Input: {1,2,3,3,4,4,5} Return value: {1,2,5}

Requirements:

  • Time: 1 s
  • Space: 64 M

Iterative method

First of all, a more “intuitive and general” idea is to use the “edge traversal edge construction” approach:

  1. Create a “virtual header node”dummyIn order to reduce the boundary judgment, the following list of answers will be connected todummyThe back;
  2. usetailRepresents the end of the currently valid linked list;
  3. Through the original inputpHeadPointers for linked list scanning.

If we iterate over the original list, we repeat the following decision (keep/skip logic) as long as the original list does not reach the end:

  • Keep:pHeadThere’s no next node,pHeadCan be reserved (insert pointer to end of answertailThe back);pHeadThere’s the next node, but the value is the same aspHeadIs not the same,pHeadCan be retained;
  • Skip over: when foundpHeadSame value as the next node, need to skip “consecutive same segment”.

Take 🌰 for example. Take the example of the title [1,2,3,3,4,4,5] and feel it in a graphic way.

  1. The value of “current node” and “next node” is different, and the current node is reserved:

  1. “Current Node” has the same value as “Next Node”, skipping “Same Contiguous Segment”, the current node cannot be retained:

Code:

class Solution { public ListNode deleteDuplication(ListNode pHead) { ListNode dummy = new ListNode(-1); ListNode tail = dummy; while (pHead ! = null) {/ / into the circulation, make sure the pHead not the same as the last node if (pHead. Next = = null | | pHead. Next, val! = pHead.val) { tail.next = pHead; tail = pHead; } // If the pHead is the same as the next node, skip the same node (reach the last bit of "consecutive same segment") while (phead.next! = null && pHead.val == pHead.next.val) pHead = pHead.next; pHead = pHead.next; } tail.next = null; return dummy.next; }}
  • Time complexity:
  • Space complexity:

The recursive method

The recursive solution method compared with the iterative solution, the code is simpler, but the difficulty of thinking is higher.

First of all, whether it is a “linked list” class title or not, before the implementation of recursion, we need to first clarify “what we expect the recursive function to accomplish”, that is, design our recursive function signature.

Obviously, we want to have a recursive function that passes in the list head, removes the repeated elements from the list, and returns the list head after the operation.

This function is the same as the deleteDuplication function that the title asked us to implement, so we just use the original function as the recursive function.

Then consider “Recursive Exit” and “Minimal Operations for Recursive Segment” :

  • Recursive exit: Consider when we no longer need the “delete” operation. Obviously when the parameter is passed inpHeadNull, orpHead.nextIs null, there must be no duplicate elements, can be returned directlypHead;
  • Minimal operations for recursive links: Later consider how the deletion logic works:
  • Obviously, whenpHead.val ! = pHead.next.valWhen,pHeadCan be retained, so we just need to takepHead.nextThe recursive function is passed in and the return value is taken aspHead.nextAnd then returnpHeadCan;
  • whenpHead.val == pHead.next.valWhen,pHeadCannot be preserved. We need to use temporary variablestmpSkip the”pHead.valValue the same in a row “, willtmpThe result of passing in the recursive function is returned as this.

Code:

Public class Solution {public listNode deleteDuplication(listNode pHead) { When the input node is empty "or" does not exist the next node ", direct return the if (pHead = = null | | pHead. Next = = null) return pHead; if (pHead.val ! Phead.next. Val) {phead.next = deleteDuplication(phead.next); phead.next = phead.next); return pHead; } else {// If the "current node" is the same as the "next node", you need to skip the "same value in a row" listNode TMP = pHead; while (tmp ! = null && tmp.val == pHead.val) tmp = tmp.next; return deleteDuplication(tmp); }}}
  • Time complexity:
  • Space complexity: Ignoring the additional space overhead caused by recursion, the complexity is

expand

  • What if the problem becomes “keep one of the same node”?

The essence doesn’t change, just grasp when the node can be retained during the traversal.

Code:

class Solution { public ListNode deleteDuplication(ListNode head) { if (head == null) return head; ListNode dummy = new ListNode(-109); ListNode tail = dummy; while (head ! = null) {// Values are not equal before appending, ensuring that only the first of the same nodes will be added to the answer if (tail.val! = head.val) { tail.next = head; tail = tail.next; } head = head.next; } tail.next = null; return dummy.next; }}
  • Time complexity:
  • Space complexity:

The last

This is the 56th article in our “Sword Finger の Selection” series, which began on January 07/01, 2012.

This series will be “sword point Offer” in the classic but outdated topics are all told again.

While providing the pursuit of “proof” & “ideas”, it also provides the most concise code.

Welcome attention, make a friend (‘ · ω · ´)