代码随想录_链表

代码随想录02

链表

203.移除链表元素

力扣题目链接(opens new window)

题意：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2： 输入：head = [], val = 1 输出：[]

示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

---

思路：

• 先判断头结点，再进行删除
• 设置一个虚拟头结点，一并删除，返回虚拟头结点的下一个节点（新的头结点）

代码：

• 法一：

class Solution {public ListNode removeElements(ListNode head, int val) {while(head != null && head.val == val) {head = head.next;}ListNode cur = head;while(cur != null && cur.next != null) {if(cur.next.val == val) {cur.next = cur.next.next;}else {cur = cur.next;}}return head;}
}

• 法二：

class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummy = new ListNode();dummy.next = head;ListNode cur = dummy;while(cur != null && cur.next != null) {if(cur.next.val == val) {cur.next = cur.next.next;}else {cur = cur.next;}}return dummy.next;}
}

707.设计链表

707. 设计链表

1. 单链表

• 设置虚拟头结点
• 增减操作要更新size

class MyLinkedList {class ListNode{int val;ListNode next;ListNode(int val) {this.val = val;}}private int size;private ListNode head;public MyLinkedList() {// head.next下标为0size = 0;head = new ListNode(0);}public int get(int index) {if(index < 0 || index >= size) return -1;ListNode cur = head;for(int i = 0;i <= index;i++) { cur = cur.next;}return cur.val;}public void addAtHead(int val) {ListNode node = new ListNode(val);node.next = head.next;head.next = node;size++;}public void addAtTail(int val) {ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = new ListNode(val);size++;}public void addAtIndex(int index, int val) {if(index < 0 || index > size) return;ListNode cur = head;for(int i = 0;i < index;i++) {// 找到index - 1cur = cur.next;}ListNode newNode = new ListNode(val);newNode.next = cur.next;cur.next = newNode;size++;}public void deleteAtIndex(int index) {if(index < 0 || index >= size) return;ListNode pre = head;for(int i = 0;i < index;i++) {// 找到index - 1pre = pre.next;// pre更新到index为i的位置, i:0 ~ index - 1}pre.next = pre.next.next;size--;}
}

2. 双链表

class MyLinkedList {class ListNode{int val;ListNode pre,next;ListNode(int val) {this.val = val;}}int size;ListNode head,tail;public MyLinkedList() {size = 0;head = new ListNode(0);tail = new ListNode(0);head.next = tail;tail.pre = head;}public int get(int index) {if(index < 0 || index >= size) return -1;ListNode cur = head;if(index >= size/2) {// 从后往前cur = tail;for(int i = size - 1;i >= index;i--) {cur = cur.pre;}}else{// 从前往后for(int i = 0;i <= index;i++) {cur = cur.next;}}return cur.val;}public void addAtHead(int val) {addAtIndex(0,val);}public void addAtTail(int val) {addAtIndex(size,val);}public void addAtIndex(int index, int val) {if(index < 0 || index > size) return;ListNode pre = head;for(int i = 0;i <= index - 1;i++) {pre = pre.next;}ListNode newNode = new ListNode(val);pre.next.pre = newNode;newNode.next = pre.next;newNode.pre = pre;pre.next = newNode;size++;}public void deleteAtIndex(int index) {if(index < 0 || index >= size) return;ListNode pre = head;for(int i = 0;i <= index - 1;i++) {pre = pre.next;}pre.next.next.pre = pre;pre.next = pre.next.next;size--;}
}

206.反转链表

206. 反转链表

1.双指针法

class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null;while(cur != null) {// 从头遍历到尾ListNode temp = cur.next; // 保存下一个cur的位置,修改cur.next指针后丢失cur.next = pre;pre = cur;// 先为pre赋值,防止cur丢失cur = temp;}return pre;}
}

2.递归法

class Solution {public ListNode reverseList(ListNode head) {return reverse(head,null);}public ListNode reverse(ListNode cur,ListNode pre) {// 1. 递归出口if(cur == null) return pre;// 2. 改变指针方向ListNode temp = cur.next;cur.next = pre;// 3. 后移return reverse(temp,cur);}
}

24.两两交换链表中的节点

24. 两两交换链表中的节点

思路:

即

1. 迭代法

class Solution {public ListNode swapPairs(ListNode head) {// 1. 初始化, 设置虚拟头结点ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode cur = dummyHead;ListNode first,second,third;// 2. 循环, 遍历交换while(cur.next != null && cur.next.next != null) {first = cur.next;second = first.next;third = second.next;cur.next = second;second.next = first;first.next = third;// cur指向下一个要处理的结点(此时first已经被移动到second的位置了)cur = first;}// 3. 返回真正的头结点return dummyHead.next; }
}

2.递归法

class Solution {public ListNode swapPairs(ListNode head) {// 1. base case 要交换的两个不能交换, 返回首节点(上一次循环的第三个结点)if(head == null || head.next == null) return head;// 2. 先往后递归, 从后往前交换ListNode next = head.next;head.next = swapPairs(next.next);// 第一个的下一个是第三个next.next = head;// 第二个的下一个是第一个// 3. 返回头结点(上一次循环中的第三个结点)return next;}
}

19.删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

• 定义fast指针和slow指针，初始值为虚拟头结点，如图：

• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
• fast和slow同时移动，直到fast指向末尾，如图： //图片中有错别词：应该将“只到”改为“直到”
• 删除slow指向的下一个节点，如图：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 1. dummyHead,f,s初始化ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode f = dummyHead,s = dummyHead;// 2. f比s多走n+1步n++;while(n-- != 0 && f != null) {f = f.next;}// 3. f s 同时走while(f != null) {f = f.next;s = s.next;}// 4. 删除s.next = s.next.next;// 5. 返回return dummyHead.next;}
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

面试题 02.07. 链表相交

面试题 02.07. 链表相交

思路:

简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。

为了方便举例，假设节点元素数值相等，则节点指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

法一: 先行移动长链表实现同步移动

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 1. 初始化, 记录ab的长度和头结点int lenA = 0,lenB = 0;ListNode curA = headA,curB = headB;// 2. 计算两链表长度, 让A记录最长的那个while(curA != null) {lenA++;curA = curA.next;}while(curB != null) {lenB++;curB = curB.next;}curA = headA;curB = headB;if(lenB > lenA) {int t = lenB;lenB = lenA;lenA = t;ListNode tn = curB;curB = curA;curA = tn;}// 3.让A与B的尾结点对齐while(lenA != lenB) {curA = curA.next;lenA--;}// 4. 遍历, 找到相同的结点, 返回while(curA != null) {// 不能用curA != curB 因为两者会同时为nullif(curA == curB) return curA;curA = curA.next;curB = curB.next;}return null;}
}

• 时间复杂度：O(n + m)
• 空间复杂度：O(1)

法二: 合并链表实现同步移动

思路：
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：

头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c 个节点；

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a+(b−c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b+(a−c)
如下式所示，此时指针 A , B 重合，并有两种情况：

a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。
因此返回 A 即可。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 1. 初始化ListNode curA = headA;ListNode curB = headB;// 2. 遍历while(curA != curB) {curA = curA != null ? curA.next : headB;curB = curB != null ? curB.next : headA;}// 3. 返回return curA;}
}

• 时间复杂度：O(n + m)
• 空间复杂度：O(1)

142.环形链表 II

142. 环形链表 II

思路:

• 判断链表是否环
  • 使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。且相遇位置就在环内.
• 如果有环，如何找到这个环的入口
  • 从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

代码:

public class Solution {public ListNode detectCycle(ListNode head) {// 1. 初始化快慢结点ListNode fast = head,slow = head;// 2. 移动快慢指针, Vf = 2*Vs, 找环(相遇的地方)while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {// 3. 找到环后, 开始找入环的第一个结点ListNode node = head;while(node != fast) {fast = fast.next;node = node.next;}// 4. 相遇结点即为所求, 返回return fast;}}// 没有找到return null;}
}