[数据结构与算法]LeetCode——链表重复元素问题、重排链表

重排链表

对一个链表，先找到后半部门的链表将其反转，然后将后半部分插入到前前半部分中，隔一个插入一个。

输入: head = [1,2,3,4]
输出: [1,4,2,3]

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

（1）用双指针找到链表的中点

（2）将后半部门利用链表反转，进行反转

（3）然后将两个链表交替进行插入

• 两个链表进行交替插入

  public void merger(ListNode l1,ListNode l2){
  	ListNode l1_temp;
  	ListNode l2_temp;
  	while(l1 != null && l2 != null){
  		l1_temp = l1.next;
  		l2_temp = l2.next;
  		
  		l1.next = l2;
  		l1 = l1_temp;
  		
  		l2.next = l1;
  		l2 = l2_temp;
  	}
  }
  

Leetcode 80. 删除有序数组中的重复项，使重复的元素只出现两次

利用快慢指针，将数组进行复制转移

public static int remove(int[] nums){
    if (nums.length <= 2){
        return nums.length;
    }
    int slow = 2;
    int fast = 2;
    while (fast < nums.length){
        if (nums[slow - 2] != nums[fast]){
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

LeetCode 82. 删除排序链表中的重复元素 II

把重复元素去掉，变成每个元素只出现一次

public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next =  head;
        ListNode p = dummy;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null){
            if(slow.val != fast.val){
                p = p.next;
                slow = slow.next;
                fast = fast.next;
            }else{
                p.next = fast;
                slow = p.next;
                fast = slow.next;
            }
        }
        return dummy.next;
    }

直接去掉链表中重复过的元素，只留下出现一次的元素

【要删除排序链表的重复节点，它的重复节点聚集在一起，可将这些重复节点视作一个要删除的节点】

public ListNode deleteDuplicates1(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode pre = h,p = head;
        while(p != null && p.next != null){
            if(p.val == p.next.val){
                while(p != null && p.next != null && p.val == p.next.val)
                    p = p.next;
                pre.next = p.next;
                p = pre.next;
            }else{
                pre = p;
                p = p.next;
            }
        }
        return h.next;
    }