LeetCode每日三題（三

一、環形鏈表

自己答案：

/*** 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){//鏈表為空直接返回falsereturn false;}int pos=-1;//定義一個集合存放鏈表ArrayList<ListNode> list=new ArrayList<>();list.add(head);//遍歷鏈表存入集合中int count=0;ListNode temp=head.next;while(temp!=null){if(!list.contains(temp)){//不存在於集合中=沒有環//繼續遍歷list.add(temp);count++;temp = temp.next;}else{//存在pos=count;return true;}}//遍歷結束則代表沒有環return false;}
}

標準答案：

快慢指針：快指針一次走兩個結點慢指針一次走一個結點若存在環則兩者遲早相遇

/*** 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){//鏈表為空直接返回falseint pos=-1;return false;}ListNode fast=head.next;ListNode slow=head;int pos=0;while(fast!=slow){//兩個指針沒有相遇（排除最開始相同的情況）if((fast==null)||(fast.next==null)||(fast.next.next==null)){//爲空結點，無環return false;}else {slow=slow.next;fast=fast.next.next;pos++;}}return true;}
}

二、環形鏈表

自己答案：

/*** 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(head==null){//鏈表為空直接返回falsereturn null;}//定義一個集合存放鏈表ArrayList<ListNode> list=new ArrayList<>();list.add(head);//遍歷鏈表存入集合中int count=0;ListNode temp=head.next;while(temp!=null){if(!list.contains(temp)){//不存在於集合中=沒有環//繼續遍歷list.add(temp);count++;temp = temp.next;}else{//存在return temp;}}//遍歷結束則代表沒有環return null;}
}

標準答案：

/*** 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(head==null){//鏈表為空直接返回falsereturn null;}ListNode fast=head;ListNode slow=head;while(fast!=null){slow=slow.next;if(fast.next==null){return null;}else{fast=fast.next.next;}if(fast==slow){ListNode temp=head;while(temp!=slow){temp=temp.next;slow=slow.next;}return slow;}}return null;}
}

三、合并兩個有序鏈表

自己答案：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list2==null&&list1!=null){return list1;}else if(list1==null&&list2!=null){return list2;}else if(list1==null&&list2==null)return null;//合并有序鏈表//分別定義兩個指針ListNode pA=list1;ListNode pB=list2;ListNode result=new ListNode(-1);ListNode temp=result;while(pA!=null&&pB!=null){if(pA.val <= pB.val) {//pA比pB小temp.next = pA;temp = temp.next;pA = pA.next;}else{temp.next = pB;temp = temp.next;pB = pB.next;}}if(pA==null){temp.next=pB;}else temp.next=pA;temp=result.next;return temp;}
}

標準答案：

递归：

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}