环形链表#141（简单）
public class Solution {public boolean hasCycle(ListNode head) {//法一:哈希表.时间复杂度O(n),空间复杂度O(n)Set<ListNode> set = new HashSet<>();while (head != null) {if (!set.add(head)) {return true;}head = head.next;}return false;}}//====================================================public class Solution {public boolean hasCycle(ListNode head) {//法二:双指针.时间复杂度O(n),空间复杂度O(1)if (head == null || head.next == null) {return false;}ListNode slow = head, fast = head.next;while (fast != slow) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;}return true;}}
环形链表Ⅱ#142（中等）
public class Solution {public ListNode detectCycle(ListNode head) {//法一:哈希表.时间复杂度O(n),空间复杂度O(n)Set<ListNode> set = new HashSet<>();while (head != null) {if (!set.add(head)) {return head;}head = head.next;}return null;}}//========================================public class Solution {public ListNode detectCycle(ListNode head) {//法二:双指针.时间复杂度O(n),空间复杂度O(1)if (head == null || head.next == null) {return null;}ListNode slow = head, fast = head;while (true) {if (fast == null || fast.next == null) {return null;}fast = fast.next.next;slow = slow.next;if (fast == slow) break;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}}
重排链表#143（中等）
class Solution {
public void reorderList(ListNode head) {
//法一:线性表.时间复杂度O(n),空间复杂度O(n)
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
//最后一个必须要置为null,否则会形成循环链表.
list.get(i).next = null;
}
}
//=============================================================
class Solution {
public void reorderList(ListNode head) {
//法二:快慢指针找中点+逆序右半边+合并链表.时间复杂度O(n),空间复杂度O(1)
if (head == null) return;
ListNode mid = middleNode(head);
ListNode list1 = head;
ListNode list2 = mid.next;
//这里一定要断开，不然会死循环
mid.next = null;
list2 = reverseList(list2);
mergeList(list1, list2);
}
//找到中点
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//逆序链表
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public void mergeList(ListNode list1, ListNode list2) {
ListNode temp1, temp2;
while (list1 != null && list2 != null) {
temp1 = list1.next;
temp2 = list2.next;
list1.next = list2;
list1 = temp1;
list2.next = list1;
list2 = temp2;
}
}
}
对链表进行插入排序#147（中等）
class Solution {
public ListNode insertionSortList(ListNode head) {
//法一:从前往后找插入点.时间复杂度O(n^2),空间复杂度O(1)
if (head == null) return null;
ListNode dummyNode = new ListNode(-1, head);
ListNode curr = head.next, lastSorted = head;
while (curr != null) {
if (lastSorted.val <= curr.val) {
lastSorted = lastSorted.next;
} else {
ListNode prev = dummyNode;
while (prev.next.val <= curr.val) {
prev = prev.next;
}
lastSorted.next = curr.next;
curr.next = prev.next;
prev.next = curr;
}
curr = lastSorted.next;
}
return dummyNode.next;
}
}
排序链表#148（中等）
class Solution {
public ListNode sortList(ListNode head) {
//法一:自顶向下归并排序.时间复杂度O(nlogn),空间复杂度O(logn)
return sortList(head, null);
}
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) return head;
if (head.next == tail) {
head.next = null;
return head;
}
ListNode slow = head, fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow;
ListNode list1 = sortList(head, mid);
ListNode list2 = sortList(mid, tail);
ListNode sorted = merge(list1, list2);
return sorted;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
//=====================================================
class Solution {
public ListNode sortList(ListNode head) {
//法一:自底向上归并排序.时间复杂度O(nlogn),空间复杂度O(1)
if (head == null) return head;
int length = 0;
ListNode node = head;
while (node != null) {
length++;
node = node.next;
}
ListNode dummyHead = new ListNode(0, head);
for (int subLength = 1; subLength < length; subLength <<= 1) {
ListNode prev = dummyHead, curr = dummyHead.next;
while (curr != null) {
ListNode head1 = curr;
for (int i = 1; i < subLength && curr.next != null; i++) {
curr = curr.next;
}
ListNode head2 = curr.next;
curr.next = null;
curr = head2;
for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
curr = curr.next;
}
ListNode next = null;
if (curr != null) {
next = curr.next;
curr.next = null;
}
ListNode merge = merge(head1, head2);
prev.next = merge;
while (prev.next != null) {
prev = prev.next;
}
curr = next;
}
}
return dummyHead.next;
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
相交链表#160（简单）
https://leetcode.cn/problems/intersection-of-two-linked-lists/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//法一:哈希表.时间复杂度O(n),空间复杂度O(n)
Set<ListNode> set = new HashSet<>();
ListNode temp = headA;
while (temp != null) {
set.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (set.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
//==================================================
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//法二:双指针.时间复杂度O(n),空间复杂度O(1)
ListNode pA = headA, pB = headB;
if (pA == null || pB == null) {
return null;
}
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
若有收获，就点个赞吧
0 人点赞
