LeetCode27. 移除元素
public int removeElement(int[] nums, int val) {
if (nums.length == 0) {
return 0;
}
// 双指针
int slow = 0, fast = 0;
while (fast < nums.length) {
nums[slow] = nums[fast];
// 当 slow 指向的数值不为目标值,两个指针一起移动
if (nums[slow] != val) {
slow++;
fast++;
} else {
// 慢指针指向的值是目标值,慢指针停下,快指针移动
fast++;
}
}
return slow;
}
时间复杂度:O(n)
空间复杂度:O(1)
LeetCode206.反转链表
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 普通的方法
// 虚拟头
ListNode dummyHead = new ListNode(-1, head);
ListNode pre = dummyHead;
ListNode cur = head;
// ListNode next = head.next;
while (cur != null) {
ListNode temp = cur.next;
cur.next = (pre == dummyHead ? null : pre);
pre = cur;
cur = temp;
}
return pre;
}
时间复杂度:O(n)
空间复杂度:O(1)
LeetCode19.删除链表的倒数第N个节点
取巧的方法,因为题目说明节点数最多只有30个,因此可以这样偷鸡
如果节点数量不明确,则不可使用
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return head;
}
// 投机取巧的方法,使用中间数组
// ∵题目中说明节点数量最多 30
ListNode[] array = new ListNode[30];
ListNode cur = head;
int len = 0;
while (cur != null) {
array[len++] = cur;
cur = cur.next;
}
int index = len - n;
// 当需要删除的位置在 0 的时候,返回 head 之后的节点即可
if (index == 0) {
return head.next;
}
ListNode pre = array[index - 1];
ListNode del = array[index];
pre.next = del.next;
del.next = null;
return head;
}
时间复杂度:O(n)
空间复杂度:O(n)
Carl 的题解:
public ListNode removeNthFromEnd(ListNode head, int n) {
// 又忘记了
// 使用双指针可以提高空间复杂度
// 快指针先走 n-1 步,之后快慢指针一起移动,当快指针指向末尾时,慢指针指向的节点就是需要删除的
// 使用虚拟头可以减少特殊情况
ListNode dummy = new ListNode(-1, head);
//int slow = 0, fast = 0;
ListNode slowN = dummy, fastN = dummy;
while (n > 0) {
fastN = fastN.next;
n--;
}
// slowN 和 fastN 一起移动,直到 fastN.next 为空
while (fastN.next != null) {
slowN = slowN.next;
fastN = fastN.next;
}
// 删除 slowN 的下一个节点
slowN.next = slowN.next.next;
return dummy.next;
}
时间复杂度:O(n)
空间复杂度:O(1)
面试题 02.07. 链表相交
这题记得,有点开心
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// 好像记得
// 首先求出两个链表各自的长度
// 再计算两个长度的差值 n,此差值就是快慢指针相差的步长
// 快指针先走 n 步,然后两个指针一起移动并开始比较
ListNode curA = headA;
int lenA = 0;
while (curA.next != null) {
curA = curA.next;
lenA++;
}
ListNode curB = headB;
int lenB = 0;
while (curB.next != null) {
curB = curB.next;
lenB++;
}
ListNode fastN, slowN;
int n = 0;
if (lenA > lenB) {
fastN = headA;
slowN = headB;
n = lenA - lenB;
} else {
fastN = headB;
slowN = headA;
n = lenB - lenA;
}
// 快指针先走 n 步
while (n > 0) {
fastN = fastN.next;
n--;
}
// 快慢指针一起走
while (fastN != null && slowN != null) {
if (fastN == slowN) {
return fastN;
}
fastN = fastN.next;
slowN = slowN.next;
}
return null;
}
时间复杂度:O(n + m)
空间复杂度:O(1)