206 .链表的反转
时间复杂度： O(n)
空间复杂度：O(1)
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
var prev = null
var curr = head
while(curr !== null){
var temp = curr.next
curr.next = prev
prev = curr
curr = temp
}
return prev
};
- 链表在指定区间的反转
如果将指定区间的链表完全翻转后再追加，需要考虑许多边界情况，处理比较复杂，现在考虑将逐一反转将m起始的每个元素逐一反转到m前面元素的后面
/**
* 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) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode start0 = dummy;
ListNode start1 = head;
for(int i = 1; i < m; i++){
start0 = start1;
start1 = start1.next;
}
for(int i = 0; i < n-m; i++){
ListNode temp = start1.next;
start1.next = temp.next;
temp.next = start0.next;
start0.next = temp;
}
return dummy.next;
}
}
160.求两个链表的交点
思路1：比较两个链表的长度，将较长的节点向后推移差值后开始遍历
思路2：设置两个指针AB，当其中一个指针走到末尾的时候从另一个指针的头节点开始遍历，直到两个指针节点相等位置，其实也是推迟较长节点的原理
时间复杂度： O（m+n）
空间复杂度： O（1）
/**
* 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 pA = headA;
ListNode pB = headB;
while(pA != pB){
pA = (pA != null)? pA.next: headB;
pB = (pB != null)? pB.next: headA;
}
return pA;
}
}
- 判断是否是循环链表
思路1：逐个遍历每个节点，并在hash table中记录每个节点的引用或内存地址。如果当前节点为null，则已经到达列表的末尾，这个链表不是循环的。如果当前节点的引用在哈希表中，就返回true
时间复杂度：O（n）
空间复杂度：O（1）
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> reserve = new HashSet<>();
while(head != null){
if(reserve.contains(head)){
return true;
}else{
reserve.add(head);
}
head = head.next;
}
return false;
}
}
思路2：用两个快慢指针，一个走一步，一个走两步，如果是循环链表的话两个链表最终会相遇
时间复杂度：O(n)
空间复杂度: O(1)
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast){
if(fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
- 返回链表循环开始的节点，如果没有，返回null
思路：设定两个快慢指针，循环之外的部分长x，循环链表长y，相遇时间为t，相遇的时候两者的路程差，即
，其中m为常数，走的较为慢的节点离循环节点的位置
，所以这个长度与循环之外的长度x相等，这个时候让慢指针回到起止节点，两个指针相遇的时候即为起始节点。
时间复杂度：O(n)
空间复杂度：O(1)
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode slow = head.next;
ListNode fast = head.next.next;
while(slow != fast){
if(fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
}
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
86.链表划分，划分后链表的相对顺序不变
思路：用两个链表分别存储小于x的一部分，存储大于x的一部分，再将两个链表拼接
时间复杂度：O(n)
空间复杂度：O(n)
注意要把right的尾节点置空，然后要判断left与t1是否相等（为空）
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null || head.next == null) return head;
ListNode left = new ListNode(0);
ListNode right = new ListNode(0);
ListNode t1 = left;
ListNode t2 = right;
ListNode p = head;
while(p != null){
if(p.val < x){
t1.next = p;
t1 = t1.next;
}else{
t2.next = p;
t2 = t2.next;
}
p = p.next;
}
t2.next = null;
if(t1 != left){
t1.next = right.next;
head = left.next;
}else{
head = right.next;
}
return head;
}
}
