锐客网

  1. 首页 > it技术 > >

删除链表中重复的节点

《剑指offer》面试题18：题目二：删除链表中重复的节点。
题目：在一个排序的链表中，如何删除重复的节点？例如，链表{1,2,3,3,4,4,5}，重复的节点删除后链表为{1,2,5}
思路：从头节点开始遍历链表，如果当前节点的值与下一个节点的值相同，那么它们就是重复的节点，都需要被删除。必须保证删除之后的链表仍然是相连的：要把当前节点的前一个节点与后面值比当前节点的值大的节点相连，中间重复的节点全部删除。如果从头节点开始就出现重复，则需要改变头节点的位置。
具体实现：定义三个节点变量：root，curNode，preNode分别代表链表的头节点，当前循环中遍历的节点，前一个节点。如果传入的头节点head为空，则直接返回头节点（即返回空）；如果头节点不为空且头节点的下一个节点为空，即链表只有一个节点，返回头节点；如果头节点和头节点的下一个节点都不为空，则依次遍历链表中的节点，如果当前节点的值与下一个节点的值相同，则继续向后遍历直到当前节点的值与下一个节点next的值不同，然后判断当前节点是不是头节点，如果是头节点，则将root指向下一个节点next作为新的头节点。最后将preNode的指针域指向当前节点的下一个节点，然后curNode跳下一位。如果当前节点的值与下一个节点的值不同，则让preNode指向当前节点，当前节点跳下一位。最后函数返回链表的头节点root。
【删除链表中重复的节点】代码如下：

// 节点类 public class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; } }// 删除链表中重复节点的方法 public ListNode deleteDuplication(ListNode head) { if (head == null || head.next == null) { return head; } // 定义三个指针分别代表头指针，当前指针，当前指针的前一个指针 ListNode root = head; ListNode preNode = head; ListNode curNode = head; // 循环遍历链表 while (curNode != null && curNode.next != null) { // 当前节点的值等于下一个节点的值即为重复 if (curNode.val == curNode.next.val) { // 向后查找所有重复的节点 while (curNode.next != null && curNode.next.val == curNode.val) { curNode.next = curNode.next.next; } // 上面循环完成之后的当前节点curNode为重复的节点，需要删除。 // 如果头指针等于当前节点，则将头指针指向当前节点的下一个节点（第一个不重复的数） if (root == curNode) { root = curNode.next; } // 让当前节点的前一个节点的next域指向当前节点的下一个节点 preNode.next = curNode.next; // 当前指针跳下一位 curNode = curNode.next; } else { // 当前节点和下一个节点不重复，则当前节点为下一次循环的前一个节点 preNode = curNode; // 当前指针跳下一位 curNode = curNode.next; } } // 返回链表头节点 return root; }

    推荐阅读


    上一篇：我们有一个习惯|我们有一个习惯 五十七

    下一篇：天下功臣