一般思路根据题意，我们可以知道链表中的元素是有序的。如果节点重复，则当前节点必须与下一个节点相同。然后，我们只需要从第一个元素开始向后比较每个元素，将节点的指针修改为非重复节点即可完成重复节点的删除。有了大概的思路，我们来梳理一下实现思路：首先，我们需要在链表的头节点之前再创建一个节点，命名为head，用来处理第一个节点和第二个节点相同的情况。其次，我们需要创建两个指针：一个指向当前的非重复节点，我们将其命名为pre，另一个是搜索指针，用于搜索与当前节点不重复的节点链表，我们将其命名为last然后，我们对pre和last进行初始化赋值：pre指向headlast指向head.next接下来我们通过while循环修改pre的指针指向其节点的下一个节点进行访问链表的每个节点，将last的指针修改为指向其节点的下一个节点，通过while循环继续访问last的下一个节点，将当前节点与下一个节点进行比较，直到出现非重复节点成立。找到一个不重复的节点后，我们修改pre的下一个节点，指向这个唯一的节点。修改last的指针指向下一个节点，继续向后探索。当last中有下一个节点，且最后一个节点的值等于下一个节点的值：否则，继续向后探索：最后返回头节点的下一个节点。（因为头节点本身就是我们创建的辅助节点，而下一个节点就是我们修改后的节点）接下来我们用文章开头的例子代入上面的思路，画一张图帮助大家更好的理解上面的思路，如下图：实现代码接下来我们将上面的思路转化为代码，如下图：/***删除链表中的重复节点*@parampHead链表头节点*/deleteDuplicatesNode(pHead:ListNode|null):ListNode|null{if(pHead==null||PHead.next==null)返回pHead;//创建头节点，处理第一个和第二个节点相同的情况consthead:ListNode={element:0,next:pHead};//创建两个指针：pre指向当前非重复节点，last是搜索指针，向后搜索找到与当前节点的非重复节点letpre=head;让last=head.next;while(last!=null){if(last.next!=null&&last.element===last.next.element){//向后查找非重复节点while(last.next!=null&&last.元素===last.next.element){last=last.next;}//将pre的指针指向一个非重复节点pre.next=last.next;//继续探索lastbackward=last.next;}else{//将指针指向其节点的下一个节点，继续向后探索pre=pre.next;最后一个=最后一个。下一个；}}返回head.next;}上面代码中的ListNode是一个自定义类型。具体代码请查看本文示例代码部分的测试用例。最后，我们将一开始的例子代入到上面的代码中，验证一下能否正确执行。从“../DeleteLinkedListNode.ts”导入{DeleteLinkedListNode}；从“../lib/LinkedList.ts”导入LinkedList；从“../utils/linked-list-models.ts”导入{printListNode}；constlistNode=newLinkedList();listNode.push(1);listNode.push(2);listNode.push(3);listNode.push(3);listNode.push(4);listNode.push(4);listNode.push(5);constpHead=deleteLinkedListNode.deleteDuplicatesNode(listNode.getHead());//输出修改后的链表节点printListNode(pHead);执行结果如下图所示：注：printListNode用于按顺序输出链表每个节点，具体代码请参考本文示例代码部分。递归思路接下来我们换个思路来解决这个问题。如果当前节点pHead等于它的下一个节点，我们添加一个指针并使用while循环修改它的指向，直到找到一个与pHead不同的节点。节点。找到后，我们将其传入递归函数，返回递归函数；如果当前节点pHead不等于它的下一个节点，我们将下一个节点传入递归函数，并修改pHead的下一个节点指向这个递归函数。最后，我们返回到pHead节点。梳理一下以上思路：判断递归基线条件：如果pHead或pHead.next为null，比较当前节点pHead和下一个节点pHead.next：如果相等，创建一个临时指针，通过继续向后探索while循环，找到相同的当前节点不重复的节点；找到之后，继续调用递归函数，将不重复的结点作为参数传入，最后返回这个递归函数。如果不相等，则修改pHead.next点，使用递归函数找到当前不相等的节点，最后返回pHead。我们把文章开头给出的例子代入到上面的思路中，画出它的递归栈，帮助大家更好的理解，如下图：实现代码接下来，我们将上面的思路转化为代码，如下所示：/***删除链表中的重复节点（递归求解）*@parampHead链表头节点*/deleteDuplicatesNodeForRecursion(pHead:ListNode|null):ListNode|null{//当节点不存在或只有1个节点时，直接返回if(pHead==null||pHead.next==null)returnpHead;//当前节点是重复节点if(pHead.element===pHead.next.element){letpNode:ListNode|null=pHead.next;//通过遍历，找到第一个不同于当前节点的节点while(pNode!=null&&pNode.element===pHead.element){//找到第一个不同于当前节点的节点pNode=pNode.next;}//本轮递归结束，从第一个与当前节点不同的节点开始递归returnthis.deleteDuplicatesNodeForRecursion(pNode);}else{//连接非重复节点pHead.next=this.deleteDuplicatesNodeForRecursion(pHead.next);//本轮递归结束，返回链表的最终头节点returnpHead;}}测试用例我们将一开始的例子代入到上面的代码中，验证是否可以正确执行。从“../DeleteLinkedListNode.ts”导入{DeleteLinkedListNode}；从“../lib/LinkedList.ts”导入LinkedList；从“../utils/linked-list-models.ts”导入{printListNode}；listNode=newLinkedList();listNode.push(1);listNode.push(2);listNode.push(3);listNode.push(3);listNode.push(4);listNode.push(4);listNode.push(5);constpHead=deleteLinkedListNode.deleteDuplicatesNodeForRecursion(listNode.getHead());//输出修改后的链表节点console.log("删除重复节点后，链表剩余节点为：");printListNode(头）；示例代码本文示例的完整代码如下：DeleteLinkedListNode.ts[1]deleteLinkedListNode-test.ts[2]LinkedList.ts[3]linked-list-models.ts[4]References[1]DeleteLinkedListNode.ts:https://github.com/likaia/algorithm-practice/blob/67dff903c1dafce96f9b7e50d9f063b25eb01c5a/src/DeleteLinkedListNode.ts#L36[2]deleteLinkedListNode-test.ts:https://github.com/likaia/algorithm-practice/blob/67dff903c1dafce96f9b7e50d9f063b25eb01c5a/src/test-case/deleteLinkedListNode-test.ts#L34[3]LinkedList.ts:https://github.com/likaia/算法实践/blob/212a5351f662ddf48bab2c289194bb09c378d9a1/src/lib/LinkedList.ts#L9[4]linked-list-models.ts:https://github.com/likaia/algorithm-practice/blob/67dff903c1dafce96f9b7e5b25f0/链表模型.ts#L29
