LeetCode刷题之旅
LeetCode刷題之旅
一、鏈表
1.鏈表逆序（leetcode 206.Reverse Linked List）esay
題目描述：已知鏈表頭節點指針head，將鏈表逆序。
思路：從鏈表的頭節點依次遍歷，每遍歷一個節點就進行逆序， 使用頭插法進行逆序。
代碼實現：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode newHead = null;while(head != null) {ListNode nextTemp = head.next;head.next = newHead;newHead = head;head = nextTemp; }return newHead;} }2.鏈表部分逆序（leedcode92.Reverse Linked List2）medium
題目描述：已知鏈表頭節點指針head，將鏈表從位置m到n逆序。
思路：需要完成m到n位置的鏈表逆序，其中逆序算法已經清楚，只需要確定開始逆序的位置（從起始節點后移m個位置），以及需要逆序的節點個數（m-n+1）。同時，需要記錄開始逆序節點的前驅（pre_start），以便逆序完可以直接鏈接上。逆置段尾結點的后繼也需要記錄。需要注意一點，討論m是否為1，如果從第一個節點開始逆置，則逆置完的鏈表段頭節點即為起始節點。
代碼實現：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {if (head == null || head.next == null) return head;ListNode pre_start, new_start, new_end;pre_start = new_start = new_end = null;ListNode list = head; //記錄listint length = n-m+1; //長度int steps = m-1;while(head!=null && steps!=0) {pre_start = head;head = head.next;steps--; //head指針移動到m對應位置}new_end = head;ListNode next_head = null;while (head!=null && length!=0) {next_head = head.next;head.next = new_start;new_start = head;head = next_head;length--; //逆序length個節點}new_end.next = head;if (m == 1) {list = new_start;} else {pre_start.next = new_start; //將pre_start鏈接上逆置后的鏈表段}return list;3.求兩個鏈表的交點（leetcode160.Intersection of Two Linked Lists）easy
題目描述：已知鏈表A的頭節點指針headA，鏈表B的頭結點指針headB，兩個鏈表相交，求兩個鏈表相交的交點
思路：1.使用set集合。遍歷鏈表A，將A中節點對應的指針（地址）存入set中。遍歷鏈表B，將B中節點對應的指針（地址），在set中查找，發現在set中的第一個節點地址，即是兩個鏈表的起始交點。
? 2.若鏈表A與鏈表B相交，則只是相交節點的前面鏈表段不相同。分別計算鏈表A與B的長度，將較長的鏈表起點移動到與短鏈表起點對齊的地方，這樣一同出發，相交點即是指針相同的交點。
代碼實現：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode listA = headA;ListNode listB = headB;int lengthA = 0;int lengthB = 0;while(headA != null) {lengthA++;headA = headA.next;} // 計算鏈表A的長度while(headB != null) {lengthB++;headB = headB.next;} // 計算鏈表B的長度int dis = 0;if (lengthB > lengthA) {dis = lengthB - lengthA;while(dis > 0){listB = listB.next;dis--;}} else {dis = lengthA - lengthB;while(dis > 0){listA = listA.next;dis--;}} //將較長鏈表的起點移動到與短鏈表起點對齊的地方while (listA!=listB && listA!=null && listB!=null) {listA = listA.next;listB = listB.next;}return listA; } }4.鏈表求環（leetcode 141.Linked List Cycle）easy
問題描述：已知鏈表可能有環，若有環則返回true，否則返回false
思路：因為只需要判斷是否有環，不用確定起始節點，所以方法較多，列舉常見的兩種。
1.利用set集合，依次將節點指針插入set中，當在set中查找，第一個在set中發現的節點地址，即是鏈表環的起點
2.從起點開始遍歷，依次判斷該節點的next是否為本身，如果是，則返回true；如果不是，則將該節點的next指針指向自己，并遞歸遍歷其后面的鏈表。
代碼實現：方法1:
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public boolean hasCycle(ListNode head) {if (head == null) return false;Set <ListNode> nodeSet = new HashSet<ListNode>(); while(head != null) {if (nodeSet.contains(head)) {return true;} else {nodeSet.add(head);head = head.next;}}return false;} }方法2：
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public boolean hasCycle(ListNode head) {if (null == head) return false;if (head == head.next) return true;ListNode n = head.next; head.next = head; // 將指針指向自己return hasCycle(n);} }5.鏈表求環2（leetcode 142.Linked List Cycle2）medium
問題描述：已知鏈表可能有環，若有環則返回環起始節點，否則返回NULL
思路：1.簡單的方法是，利用set集合實現。依次將節點指針插入set中，當在set中查找，第一個在set中發現的節點地址，即是鏈表環的起點。
? 2.相對巧妙的想法，利用快慢指針實現。見下面，fast與slow指針同時從起點X出發，其中fast是slow速度的兩倍，當fast指針追到slow指針時，此時相遇于Z點。對于slow指針，走了a+b的路程。那么fast指針的路程為2（a+b），同時也為 a+b+c+b，即a+2b+c=2(a+b)，得a=c。這時，如果從它們的交點Z出發的話，同時有一指針head從起點X出發，必會相交于Y點，也即為環的起始點。
代碼實現：方法1
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public ListNode detectCycle(ListNode head) {// if (null == head) return null;Set<ListNode> nodeSet = new HashSet<ListNode>();while(head != null) {if (nodeSet.contains(head)) {return head;} else {nodeSet.add(head);}head = head.next;}return null;} }方法2：
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public ListNode detectCycle(ListNode head) { ListNode fast = head;ListNode slow = fast;while (fast!=null && fast.next!=null && fast.next.next!=null) { fast = fast.next.next;slow = slow.next;if (fast == slow) { // fast與slow指針相交時while (head != slow) {head = head.next; // head指針從起始點出發slow = slow.next;}return head;} }return null;} }6.鏈表劃分（leetcode86.Partition List）medium
問題描述：已知鏈表頭指針head與數值x，將所有小于x的節點放在大于等于x的節點前，且保存這些節點的原來的相對位置。如，劃分前：1->4->3->2->5->2，x=3，劃分后：1->2->2->4->3->5
思路：遍歷鏈表，將小于x的節點插入到新鏈表less_head中，將大于等于x的節點插入到新鏈表more_head中，然后將more_head.next插入在less_head的末尾，返回less_head即可。
或者直接將原鏈表中大于x的節點移出并鏈接為新鏈表mhead，然后將mhead鏈接至原鏈表的結尾即可。
代碼實現：方法1
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode partition(ListNode head, int x) {ListNode lhead = new ListNode(0); // 使用兩個鏈表less_head和more_head來分別記錄ListNode less_head = lhead; ListNode mhead = new ListNode(0);ListNode more_head = mhead;while(head!=null) {if (head.val < x) {lhead.next = head;lhead = lhead.next;} else {mhead.next = head;mhead = mhead.next;}head = head.next;}mhead.next = null;lhead.next = more_head.next;return less_head.next;} }方法2：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode partition(ListNode head, int x) { ListNode list = new ListNode(0); // 將原鏈表中大于x的值連接為一個鏈表mheadlist.next = head;ListNode new_head = list;ListNode more_head = new ListNode(0);ListNode mhead = more_head;while(list.next!=null) {if (list.next.val < x) {list = list.next;} else {more_head.next = list.next;more_head = more_head.next;list.next = list.next.next; }}list.next = mhead.next;more_head.next = null;return new_head.next;} }7.鏈表的深度拷貝（leetcode138.Copy List With Random Pointer）medium
問題描述：已知一個復雜的鏈表，鏈表節點除了有一個指向下一個節點的next指針，還有一個random指針，指向本鏈表的任意某個節點（也可能指向自己），求這個鏈表的深度拷貝（構造生成一個完全新的鏈表，即使原鏈表毀壞，新鏈表也可獨立使用）
思路：本問題中，主要是一個random指針也需要拷貝下來。利用map來實現，其中map的key記錄原鏈表的各個節點，value來保存新建的節點（val值為key中節點的值），對于新建的節點的next和random指向的節點位置，由對應的key獲得。即，map.get(head).next = map.get(head.next)、map.get(head).random = map.get(head.random)。
代碼實現：
/* // Definition for a Node. class Node {public int val;public Node next;public Node random;public Node() {}public Node(int _val,Node _next,Node _random) {val = _val;next = _next;random = _random;} }; */ class Solution {public Node copyRandomList(Node head) {if (head == null) return null;Map<Node, Node> map = new HashMap<>();Node iter = head;while(iter != null) {map.put(iter, new Node(iter.val));iter = iter.next;} // 將鏈表的各個節點指針存為map的key，value為該節點的拷貝。iter = head;while(iter != null) {map.get(iter).next = map.get(iter.next);map.get(iter).random = map.get(iter.random);iter = iter.next;}return map.get(head);} }8.排序鏈表的合并（2個）（leetcode21.Merge Two Sorted Lists）easy
問題描述：已知兩個已排序鏈表頭結點l1和l2，將這兩個鏈表合并，合并之后仍是有序的，返回合并后鏈表頭節點。
思路：本題相對簡單，依次比較l1和l2的頭結點，誰小就將誰插入新鏈表l中。最后返回l鏈表即可。
代碼實現：方法1
/*** 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 l = new ListNode(0);ListNode head = l;while(l1!=null && l2!=null) {if (l1.val < l2.val) {head.next = l1;head = head.next; l1 = l1.next;} else {head.next = l2;head = head.next;l2 = l2.next;}}if (l1 != null) head.next = l1; // 如果l1還有剩余節點，直接鏈接到l后面else head.next = l2; // l2還有剩余return l.next;} }方法2（遞歸實現）：
/*** 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) { if(l1 == null) return l2;if(l2 == null) return l1;if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next, l2);return l1;} else{l2.next = mergeTwoLists(l1, l2.next);return l2;}} }9.排序鏈表的合并（多個）（leetcode23.Merge K Sorted Lists）hard
問題描述：已知k個已排序鏈表頭結點l1和l2，將這k個鏈表合并，合并之后仍是有序的，返回合并后鏈表頭節點。
思路：本題相當于上一題難度變大，主要是如何分配這k個鏈表，讓其分別兩兩合并，最后合并為一個整體。如果采用暴力破解，從第一個開始，合并第二個，然后再合并第三個。。。，共k個鏈表，平均每個鏈表有n個節點，則時間復雜度為：(n+n)+(2n+n)+(3n+n)+…+((k-1)n+n) = (1+2+3+…+k-1)n+(k-1)n = (k^2+k-1)/2*n = O(k^2 *n).
另一個思路，采用分治法，即兩兩進行合并。第一輪，進行k/2次，每次處理2n個；第二輪，進行k/4次，每次處理4n個，…，最后一次，進行k/(2logk)次，每次處理2logk*n個值。時間復雜度為：k/2 *2n+k/4 *4n+…+k/(2^logk) *(2^logk *n) = nk+nk+…+nk = O(klogk * n)。
代碼實現：
利用數組實現：
/*** 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 mid = lists.length/2;ListNode[] lists1 = new ListNode[mid];for (int i=0; i<mid; i++) { // 將lists前半部分存入數組list1[]中lists1[i] = lists[i];}ListNode[] lists2 = new ListNode[lists.length-mid];for (int i=mid; i<lists.length; i++) { // 將lists后半部分存入數組list2[]中lists2[i-mid] = lists[i];} ListNode sub_list1 = mergeKLists(lists1); // 將list1[]中鏈表合并ListNode sub_list2 = mergeKLists(lists2); // 將list2[]中鏈表合并return mergeTwoLists(sub_list1, sub_list2);}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}} }總結
以上是生活随笔為你收集整理的LeetCode刷题之旅的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 前端学习之html——基本结构
- 下一篇： linux操作系统分析实验—基于myke