LeetCode刷题日志（一）

谁践踏了优雅 2022-03-06 11:44 184阅读 0赞

虽然之前对java的各方面应用有了拓展的了解，但是发现自己的短板依旧很明显就是算法。之前虽然有看过算法课，但是实际的coding却没有做太多。所以从今天起，每天都要ac一些题目然后进行总结。把ac过程中自己不会的知识点记录并深化。

我选择从LeetCode上写题，他的难度适中。然后很符合公司出题标准，我打算按照LeetCode提供的分类进行刷题。

**目录**

链表篇

1.合并两个有序链表

2.合并k个链表

3.k个一组翻转链表

4.排序链表

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

# 链表篇 #

## 1.合并两个有序链表 ##

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

这道题是在数据结构学习中最开始就接触过。这也是归并法的雏形，原理就是设置一个临时的指针。然后比较两个链表的头结点值大小，让临时指针的下一个位置指向其中较小的值。需要注意的是指针在遍历中的变化。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
          ListNode temp = new ListNode(0);
    	        ListNode head = temp;
    	        while(l1!= null && l2 !=null){
    	        	if(l1.val<l2.val){
    	        		head.next = l1;
    	        		l1 = l1.next;
    	        	}else{
    	        		head.next = l2;	        		
                        l2 = l2.next;
    	        	}
                  head = head.next;
    	        }
    
    	        head.next = l1 == null?l2:l1;
    	        return temp.next;  
        }
    }

##  2.合并k个链表 ##

合并 *k *个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

**示例:**

输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6

这道题是上一道题的加强版，这道题有很多种解法，我们可以把k个链表的前两个进行合并，然后依次和后面的所有链表挨个进行合并，将它转化为合并两个链表。但是这并不高效。解决这道题的办法可以参考归并排序，这道题传入的参数是一系列链表的头结点数组。我们可以采用归并排序中的思路讲这数组进行划分，分治排序然后进行归并整合。

首先将整个大的数组分成长度相同的两个数组。

int middle = lists.length/2;
    ListNode[] sub_list1 = new ListNode[middle];
    ListNode[] sub_list2 = new ListNode[lists.length-middle];
    for(int i = 0;i<middle;i++)
    	sub_list1[i] = lists[i];
    for(int i = 0;i<lists.length-middle;i++)
    	sub_list2[i] = lists[i+middle];

之后采用分治法对每个子数组再次进行排序

ListNode l1 =  mergeKLists(sub_list1);
    ListNode l2 =  mergeKLists(sub_list2);

最后需要将以l1和l2为头结点的链表进行归并排序

return mergeTwoLists(l1,l2);

当然如果传入的结点链表为空，只有一个或者两个结点，是需要进行特殊处理的，也就是递归的结束条件。

if(lists.length == 0)
    		   		return null;
    		   if(lists.length == 1)
    			   return lists[0];
    		   if(lists.length == 2)
    			   return mergeTwoLists(lists[0],lists[1]);

下方是我的完整代码

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
     public ListNode mergeKLists(ListNode[] lists) {
    		   	if(lists.length == 0)
    		   		return null;
    		   if(lists.length == 1)
    			   return lists[0];
    		   if(lists.length == 2)
    			   return mergeTwoLists(lists[0],lists[1]);
    		   int middle = lists.length/2;
    		   ListNode[] sub_list1 = new ListNode[middle];
    		   ListNode[] sub_list2 = new ListNode[lists.length-middle];
    		   for(int i = 0;i<middle;i++)
    			   sub_list1[i] = lists[i];
    		   for(int i = 0;i<lists.length-middle;i++){
    			   sub_list2[i] = lists[i+middle];
    		   }
    		  ListNode l1 =  mergeKLists(sub_list1);
    		  ListNode l2 =  mergeKLists(sub_list2);
    	       return mergeTwoLists(l1,l2);
    	    }
    	   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	        ListNode temp = new ListNode(0);
    	        ListNode head = temp;
    	        while(l1!= null && l2 !=null){
    	        	if(l1.val<l2.val){
    	        		head.next = l1;
    	        		head = l1;
    	        		l1 = l1.next;
    	        	}else{
    	        		head.next = l2;
    	        		head = l2;
    	        		l2 = l2.next;
    	        	}
    	        }
    	        head.next = l1 == null?l2:l1;
    	        return temp.next;
    	    }
    }

## 3.k个一组翻转链表 ##

这道题我是参照别人写出的代码进行ac的，但是我将它的思路并复现了代码

给出一个链表，每 *k *个节点一组进行翻转，并返回翻转后的链表。

*k *是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 *k *的整数倍，那么将最后剩余节点保持原有顺序。

**示例 :**

给定这个链表：`1->2->3->4->5`

当 *k *= 2 时，应当返回: `2->1->4->3->5`

当 *k *= 3 时，应当返回: `3->2->1->4->5`

**说明 :**

*  你的算法只能使用常数的额外空间。
 *  **你不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。

涉及到链表的翻转，右移这些问题都是有规律的。都是链表的某一部分按照规律进行移动，剩余的部分按照相同的方式进行移动。参照这道题，将链表中每k个元素进行翻转，如果最后剩余部分不足k个则不进行翻转。反转链表我们都知道怎么去做。这个里面就是递归地从某一个结点开始到某一个结点结束进行区间的翻转。

那么现在我就讲述一下这道题的思路，在开始翻转区间链表之前，需要找到开始和结束的位置。开始的位置就是上一次结束位置的下一个结点，结束的位置就是当前结点向后数k-1个位置。首先需要判断剩余长度是否可以进行反转。

while(canProceed<k&&check!=null){
    			check = check.next;
    			canProceed++;
    		}//判断剩下的链表长度是否满足反转条件

canProceed初值为0，当跳出循环时只有canProceed等于k才说明剩余部分可以进行反转，如果可以反转。那么剩余部分就是

\[cur,check)区间的链表反转。

while(cur != check){
    				 next = cur.next;
    				 cur.next = prev;
    				 prev = cur;
    				 cur = next;
    			 }

注意这里面的next指针，next指针在结束的时候指向的就是check，也就是下一个区间的头结点的位置，只有该结点不为null才可以进行下一个区间的翻转。如果next为null，返回prev结点，这个prev结点本来是之前那个区间链表没有翻转时的尾节点，但是在完成翻转后，它就变成了头结点，这个头结点就是之前翻转链表的尾节点的下一个结点。

head.next = mycode(next,k);

当然如果发现canProceed和k不相等，说明剩余部分链表不能进行翻转，那么直接将头结点进行返回即可。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
         public ListNode reverseKGroup(ListNode head, int k) {
    	        ListNode prev = null;
    	        ListNode cur = head;
    	        ListNode next = null;
    	        ListNode check = head;
    	        int canProceed = 0;
    	        int count = 0;
    	        // 检查链表长度是否满足翻转
    	        while (canProceed < k && check != null) {
    	            check = check.next;
    	            canProceed++;
    	        }
    	        // 满足条件，进行翻转
    	        if (canProceed == k) {
    	            while (cur != check) {
    	                next = cur.next;
    	                cur.next = prev;
    	                prev = cur;
    	                cur = next;
    	                count++;
    	            }
    	            if (next != null) {
    	                // head 为链表翻转后的尾节点
    	                head.next = reverseKGroup(next, k);
    	            }
    	            // prev 为链表翻转后的头结点
    	            return prev;
    	        } else {
    	            // 不满住翻转条件，直接返回 head 即可
    	            return head;
    	        }
    	    }
    }

## 4.排序链表 ##

在 *O*(*n* log *n*) 时间复杂度和常数级空间复杂度下，对链表进行排序。

**示例 1:**

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

**示例 2:**

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

按照题目的要求，我们不能使用辅助数组，而且时间复杂度也是nlogn。那么这道题同样使用的是归并排序的思路，只是这道题有个坑我想指出来给我自己警示。

大体的思路很简单，归并之前也提到了。

坑的地方就是这里

ListNode slow = head, fast = head, pre = head;
    	        while (fast != null && fast.next != null) {
    	            pre = slow;
    	            slow = slow.next;
    	            fast = fast.next.next;
    	        }
    	        pre.next = null;//将原先的链表分成两个部分

这里通过快慢指针将链表分成两个部分。慢指针是右侧链表的头结点，head是左侧链表的头结点。至于这个pre，它是左侧链表的尾节点，作为尾节点一定要将它的next置为null。第一次写时没有注意到这一点导致了栈的溢出。特此指出给自己进行警示。

代码很好理解我就不再详细说明了，主要是理解快慢指针将数组进行等分的原理。

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
      public ListNode sortList(ListNode head) {
    	     if(head == null || head.next == null)
    	    	 return head;
    	     ListNode slow = head, fast = head, pre = head;
    	        while (fast != null && fast.next != null) {
    	            pre = slow;
    	            slow = slow.next;
    	            fast = fast.next.next;
    	        }
    	        pre.next = null;
    		 ListNode leftHead = sortList(head);
    		 ListNode rightHead = sortList(slow);
    		 return merge(leftHead,rightHead);
    	    }
    	private ListNode merge(ListNode leftHead, ListNode rightHead) {
    		ListNode temp = new ListNode(-1);//辅助结点
    		ListNode ptr = temp;
    		while(leftHead != null && rightHead != null){
    			if(leftHead.val<rightHead.val){
    				ptr.next = leftHead;
    				leftHead = leftHead.next;
    			}else{
    				ptr.next = rightHead;
    				rightHead = rightHead.next;
    			}
    			ptr = ptr.next;
    		}
    		if(leftHead == null)
    			ptr.next = rightHead;
    		if(rightHead == null)
    			ptr.next = leftHead;
    		return temp.next;
    	}
    }

时间和篇幅的问题我只在这里写出了四道题的思路，虽然有些是借鉴别人的思路，但我没有直接粘贴别人的代码。而是根据自己的理解一点点写了出来并进行调试。

2019年3月18日22:18:13