LeetCode题集——分割链表 + 删除排序链表中的重复元素(1+2)

目录

题目一：分割链表

解法一： 双指针

 解法二：头插法

 题目二：删除排序链表中的重复元素

解法一：单指针

解法二：快慢指针

 解法三：递归

题目三：删除排序链表中的重复元素(2)

---

题目一：分割链表

具体要求：

解法一： 双指针

将小于特定值，与大于等于特定值分为两组，然后将二者拼接起来，返回新链表即可

不理解？看图：

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode List1=new ListNode(0);
        ListNode List2=new ListNode(0);
        ListNode list1=List1;
        ListNode list2=List2;
        while(head!=null) {
            if(head.val<x) {
                list1.next=head;
                list1=list1.next;
            } else {
                list2.next=head;
                list2=list2.next;
            }
            head=head.next;
        }
        list2.next=null;
        list1.next=List2.next;
        return List1.next;
    }
}

测试通过：

 解法二：头插法

遍历链表，将每个小于特定值的节点头插到链表头部

class Solution {
    public ListNode partition(ListNode head, int x) {
       ListNode dummy = new ListNode();
        dummy.next = head;
        while (head != null && head.next != null) {
            int nextVal = head.next.val;
            if (nextVal < x) {
                ListNode next = head.next;
                head.next = head.next.next;
                next.next = dummy.next;
                dummy.next = next;
            } else {
                head = head.next;
            }
        }
        return dummy.next;
 
 
    }
}

测试通过：

 题目二：删除排序链表中的重复元素

具体要求：

解法一：单指针

将链表遍历一遍，因为链表的数据是有序的，所以只要当前数据与下一个数据相同，则删除当前的下一个节点即可。 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur=head;
        while(cur!=null&&cur.next!=null) {
            if(cur.val==cur.next.val) {
                cur.next=cur.next.next;
            } else {
                cur=cur.next;
            }
        }
        return head;
    }
}

测试通过：

解法二：快慢指针

思路其实很解法一相似，只不过呈现形式不同罢了，快慢指针，是判断快慢指针所指向的数据是否相同，若相同，则跳过快指针对应的节点。 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
       
        if(head==null||head.next==null) {
            return head;
        }
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null) {
            if(fast.val==slow.val) {
                slow.next=fast.next;
                fast=fast.next;
            } else {
                fast=fast.next;
                slow=slow.next;
            }
        }
        
        return head;
    }
}

测试通过：

 解法三：递归

链表具有天然的递归性，链表看成其头节点后挂接一个更短的链表，这个更短的链表看成其头节点后面挂接一个更更短的链表，依次类推。

1、删除更短链表中所有重复的元素；

2、判断原链表的头节点的值是否等于经过第 1 步处理后的更短链表头节点的值；

3、若相等，则返回更短的链表；

4、否则，将更短的链表挂接在原链表的头节点的后面，再返回。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        //递归终止条件
        if(head==null||head.next==null) {
            return head;
        }
        //递归调用,删除
        head.next=deleteDuplicates(head.next);
        return head.val==head.next.val?head.next:head;
 
    }
}

测试通过：

题目三：删除排序链表中的重复元素(2)

题目具体要求：

注意与上一道题的区别，这里是将重复数字删除，如1,1,1,2，则结果中将所有1删除，输出：2，而上一道题中，会保留一个1，输出：1，2

大致思路：

 

 代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null) {
            return head;
        }
        ListNode cur=new ListNode();
        cur.next=head;
        ListNode pre=cur;
        while(pre.next!=null&&pre.next.next!=null) {
            int val=pre.next.val;
            if(pre.next.next.val==val) {
                while(pre.next!=null&&pre.next.next!=null&&pre.next.next.val==val) {
                    pre.next=pre.next.next;
                }
                pre.next=pre.next.next;
            } else {
                pre=pre.next;
            }
        }
        return cur.next;
    }
}

代码重点注意：

• 需要一个虚拟头节点，原因：如果第一个数就是重复数字，即头节点发生变化，并且无法确定，头节点需要往后移几个，所以采用虚拟头节点，使第一个数就是重复数字的这个特例就可以划分为普通情况了
• 记录数值val，判断后一个数值是否相等，如果相等，则开始删除，否则，往后移一个节点，继续判断。
• 为什么令pre.next.val等于val？原因：我们需要删除所有重复数字（一个不留），所以在删除节点时，我们需要使用该值所在节点的前一个结点，即需要给pre.next重新赋值的。
• 删除时，我们无法确定有几个连续重复出现的数字，因此在if中嵌套了一个while循环，注意在循环中可能会出现空指针，因此需要加上限定判断其不为null
• 删除时，我们每次只删除一个节点，当while（第二个）结束时，还残留了一个节点未删除，所以在while结束后，再删除一个节点。

下期见！！！