【链表第七篇】链表去重两个题目

文章目录

• • • 82. 删除排序链表中的重复元素 II
    • • 问题描述
      • 解法1：一个指针
      • 解法2：快慢指针
      • 解法3：递归法（链表都可以用递归法来解决）
    • 83. 删除排序链表中的重复元素
    • • 单个指针，一次解决
    • 61,旋转链表
    • • 题目描述
      • 解决方案（算出移动次数 + 算出用哪个做头结点 + 算出断开那个指针）

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

这句是重点：说明只要不需要新建一个链表，只要在原链表对元素去重就好了，C++需要释放内存，Java更简单，直接改变指针指向就好了，需要删除的节点就跳过，这样遍历就不会有这个节点了。

示例 1：

输入：head = [1,2,3,3,4,4,5]

输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]

输出：[2,3]

class Solution {
    public ListNode deleteDuplicates(ListNode head) {     
      ListNode first = new ListNode(-1,head);
      ListNode p=first;
      while(p.next!=null && p.next.next!=null){
          if(p.next.val == p.next.next.val){  // 触发删除动作
             int x=p.next.val;  // 后面p.next会改变，所以先记录这个p.next的val值
             while(null != p.next && x == p.next.val)     // 执行删除动作,p.next是要被删除的节点，p.next.val是要被删除的节点的值，这个值要和后面的值比较
                 p.next = p.next.next;  // 链表中跳过p.next节点
          }else{
              p = p.next; 
          }
      }
      return first.next;   //  这里貌似不能return head;
    }
}
           

注意两行代码：

第一，内层循环必须

while(null != p.next && x == p.next.val)

不能

while( x == p.next.val)

因为要保证while循环的后半句

x == p.next.val

，如果null == p.next， p.next.val会报空指针。

因为要保证

p.next = p.next.next;

语句的安全，如果null == p.next， p.next.next会报空指针。

第二，最后是return first.next;不是return head;

如果return head;那么对于

输入：[1,1,1,2,3]，预期结果：[2,3]

但是输出：[1,1,1,2,3]

一图解释：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode first = new ListNode(-1, head);
        ListNode curNode = first;   // 快指针，相当于单个指针的p值指针
        ListNode preNode = first;  // 慢指针,快慢指针都从虚拟头结点first出发
        while(curNode.next != null){   // 快指针
            if(curNode.next.next != null && curNode.next.val == curNode.next.next.val){   // 判断重复元素
                curNode = curNode.next;  // 快指针每次循环都走一次
                while(curNode.next != null && curNode.val == curNode.next.val){  // 删除重复元素
                    curNode = curNode.next;   // 删除元素是时候没有使用改变指针指向的方式，这个操作又慢指针来完成，即preNode.next=curNode.next
                }
                preNode.next = curNode.next;  // 慢指针指向
            }else{
                preNode = curNode.next;  // 慢指针到快指针后一个元素
                curNode = curNode.next;   // 快指针继续移动一个元素
            }
        }
        return first.next;   // 这里不能返回head,否则会出现[1,1,1,2,3]的实例错误
    }
}
           

while(curNode.next != null && curNode.val == curNode.next.val)

while(curNode.val == curNode.next.val)

因为要保证 while循环的后半句

curNode.val == curNode.next.val

语句的安全，如果输入为[1,1]，这里会出现空指针如果null == curNode.next，curNode.next.val会报空指针。

其实，else中的代码块也可以写成这样，只要else块中两个指针指向同一个节点，和开始的时候一样（开始的时候都指向first节点），接着移动就行。

curNode = curNode.next;   // 快指针继续移动一个元素
preNode = curNode;  // 慢指针到快指针后一个元素
           

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head!=null) {  // 为null直接return null,不为null走下面的
            ListNode p = head;  // 从实际头结点开始
            while (p.next != null && p.next.val == p.val)  //p.next!=null 保证后半句的安全 
                p = p.next;   // 如果p指向的和下一个相同，就不断后移动
            if (p == head)  // 分情况讨论，如果
                head.next = deleteDuplicates(head.next);
            else
                head = deleteDuplicates(p.next);
        }
        return head;
    }
}
           

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

输入：head = [1,1,2]

输出：[1,2]

输入：head = [1,1,2,3,3]

输出：[1,2,3]

class Solution {
    public ListNode deleteDuplicates(ListNode head) {     
      if(head == null || head.next==null) return head;   // first虚拟头结点和head 0个/1个元素判断 两个选一个就好
      ListNode p=head;
      while(p.next!=null && p!=null){
          if(p.val == p.next.val){  // 触发删除动作
             while(null != p.next && p.val == p.next.val)     // 执行删除动作,p.next是要被删除的节点，p.next.val是要被删除的节点的值，这个值要和后面的值比较
                 p.next = p.next.next;  // 链表中跳过p.next节点
          }else{
              p = p.next; 
          }
      }
      return head; 
    }
}
           

82题不使用虚拟头结点难受，使用虚拟头结点爽

难受1：因为比较的对象是 p.next.val 和 p.next.next.val，如果不使用虚拟头结点，p=head，第一个节点会被遗漏，这个问题几乎无法处理。

难受2：不使用虚拟头结点，即使加上了

if(head==null || head.next==null)

排除零个节点和一个节点，但是对于链表只有两个节点的特殊情况，无法被第一句处理，也无法进入 while(p.next!=null && p.next.next!=null) 的循环中，

爽1：因为比较的对象是 p.next.val 和 p.next.next.val，如果不使用虚拟头结点，ListNode first = new ListNode(-1,head); LinkList p=first，虚拟头结点在比较中遗漏（反正也需要被比较），比较从第一个节点和第二个节点开始。

爽2：使用虚拟头结点，加上了

if(head==null || head.next==null)

排除零个节点和一个节点，对于链表只有两个节点的特殊情况，可以进入到 while(p.next!=null && p.next.next!=null) 的循环中，

83题不使用虚拟头结点爽，使用虚拟头结点难受

难受1：因为比较的对象是 p.val 和 p.next.val，如果使用虚拟头结点，虚拟头结点也被用于参与比较。

爽1：因为比较的对象是 p.val 和 p.next.val，如果不使用虚拟头结点，虚拟头结点不会被用于参与比较，对于零个节点和一个节点的情况，加上

if(head==null || head.next==null)

这一句就好了。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null) return head;
        int length = 1;  // 因为已经是从head开始了，所以length从1开始
        ListNode p=head;
        while (p.next!=null){
            p=p.next;
            length++;
        }
        if(k%length ==0) return head;

        int lastIndex=k%length;
        int index = length - lastIndex;  // 5-2=3  第三个节点的指针要设置为null

        // 得到第四个节点的指针

        ListNode resultPoint=head;  // 因为已经是从head开始了，所以resultCount从1开始
        int resultCount=1;
        while(resultCount<(index+1)){
            resultPoint=resultPoint.next;
            resultCount++;
        }

        // 修改原来链表 p指针指向单链表尾部,就是尾指针了
        p.next = head;  
        int count=0;   // 因为已经是从尾节点开始，所以count从0开始
        while(count < index){  // 等于index退出
            p=p.next;
            count++;  // 到达第一个节点，加一，达到第二个节点，再加一
        }
        p.next=null;

        return resultPoint;

    }
}