LeetCode刷题日志（二）

「爱情、让人受尽委屈。」 2022-02-28 20:44 148阅读 0赞

昨天有些事情耽误了笔记的总结，今天要补上。

上一次分析了关于链表的一些问题，我主要以模块来划分题型。这次我再总结几道关于链表的题目，链表的题目我打算告一段落。

**目录**

1.将有序数组转换为二叉搜索树

2.有序链表转换二叉搜索树

3.删除排序链表中的重复元素

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

--------------------

## 1.将有序数组转换为二叉搜索树 ##

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1。

**示例:**

给定有序数组: [-10,-3,0,5,9],
    
    一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

这道题是比较基础的一道题，这道题也是运用了递归的思想，分别对左子树和右子树进行递归的构造。通过观察发现，一个节点的左子树都在它的左侧，他的右子树都在它的右侧部分。那么可以这样考虑，一个节点的左孩子是它左侧区间的中点，右孩子是它右侧区间的重点。当这个区间的左值大于右值时，递归结束，返回null。说明这个节点是根节点。

public TreeNode sortedArrayToBST(int[] nums) {
    		if(nums.length == 0)
    			return null;
    		return getBST(nums,0,nums.length-1);
    	    }
    	private TreeNode getBST(int[] nums, int left, int right) {
    		if(left > right)
    			return null;
    		int middle = left+(right-left)/2;
    		TreeNode head = new TreeNode(nums[middle]);
    		head.left = getBST(nums, left, middle-1);
    		head.right = getBST(nums,middle+1,right);
    		return head;
    	}

## 2.有序链表转换二叉搜索树 ##

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1。

**示例:**

给定的有序链表： [-10, -3, 0, 5, 9],
    
    一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
    
          0
         / \
       -3   9
       /   /
     -10  5

这道题的思路和上一道题是相同的，都是将链表进行二分。需要注意的就是我在上一次leetcode笔记中提到的链表的二分中需要将最后一个节点的next域置为null。

public TreeNode sortedListToBST(ListNode head) {
    		  if(head == null )
    				return null;
    		  if(head.next == null)
    			  return new TreeNode(head.val);
    			ListNode slow = head;
    			ListNode fast = head;
    			ListNode pre = null;
    			while(fast!=null&&fast.next!=null){
    				pre = slow;
    				slow = slow.next;
    				fast = fast.next.next;
    			}
    			pre.next = null;//将链表分成两个部分
    			TreeNode treehead = new TreeNode(slow.val);
    			treehead.left = sortedListToBST(head);//左子树是以左侧部分链表进行递归
    			treehead.right = sortedListToBST(slow.next);//右子树是以右侧部分开始递归
    			return treehead;
    	    }

之前的问题基本上都是和链表的顺序调整有关，接下来我遇到了链表的删除问题。

## 3.删除排序链表中的重复元素 ##

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

**示例 1:**

输入: 1->1->2
    输出: 1->2

**示例 2:**

输入: 1->1->2->3->3
    输出: 1->2->3

思路非常简单，找到重复元素的第一个元素，将这个元素的next域指向和重复元素不相同的第一个结点。拿1->1->2来举例。找到了第一个1，然后去查找2。让1的next域指向2。

public ListNode deleteDuplicates(ListNode head) {
           if(head == null)
        	   return head;
    		ListNode pre = null;
            ListNode ptr = head;
            while(ptr!=null){
            	pre = ptr;
            	ptr = ptr.next;
            	//进行删除判断
            	while(ptr!=null&&pre.val == ptr.val){
            		//将ptr删除
            		pre.next = ptr.next;
            		ptr = ptr.next;
            	}
            }
            return head;
        }

pre指针总是指向重复元素序列的第一个位置。删除完毕后令pre移动到ptr的位置进行重复的循环查找过程。

## 4.删除排序链表中的重复元素 II ##

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 *没有重复出现 *的数字。

**示例 1:**

输入: 1->2->3->3->4->4->5
    输出: 1->2->5

**示例 2:**

输入: 1->1->1->2->3
    输出: 2->3

这道题和上一道题不同的地方就是要将重复的元素全部进行删除。那么这样子就需要一个新增的指针pre\_pre。这个指针总是指向pre的前一个位置，因为上一道题中，pre是重复元素序列的第一个位置，那么pre\_pre只需要指向重复元素序列结束后的那个元素即可。

public ListNode deleteDuplicates(ListNode head) {
    		 if(head == null)
    	    	   return head;
    			ListNode pre = null;
    			ListNode pre_pre = null;
    	        ListNode ptr = head;
    	        while(ptr!=null){
    	        	pre = ptr;
    	        	ptr = ptr.next;
    	        	if(ptr!=null&&pre.val != ptr.val){
    	        		pre_pre = pre;
    	        	}
    	        	//进行删除判断
    	        	while(ptr!=null&&pre.val == ptr.val){
    	        		//将ptr删除
    	        		pre.next = ptr.next;
    	        		ptr = ptr.next;
    	        		if(pre_pre == null)
    		        		head = ptr;
    		        	else{
    		        		pre_pre.next = ptr;
    		        	}	
    	        	}
    	        }
    	        return head;
        }

对于这个代码我进行一下分析

if(ptr!=null&&pre.val != ptr.val){
    	        		pre_pre = pre;
    	        	}

如果没有重复的元素，pre\_pre要跟住pre。这样在开始删除的时候，pre\_pre对应的就是重复序列的前一个元素。

删除的时候需要对pre\_pre进行调整。

if(pre_pre == null)
    		        		head = ptr;
    		        	else{
    		        		pre_pre.next = ptr;
    		        	}

这么做的目的是防止这种情况 1->1->1->2->3。这样在开始删除时pre\_pre的值为null。当然这种情况很简单，只需要改变head结点的位置即可。

关于链表我暂时总结了这么多我认为具有代表性的问题供自己参考以及学习。