链表
今天主要是把链表专题刷完了,链表专题的题目不是很难,基本都是考察对链表的操作的理解。
在处理链表问题的时候,我们通常会引入一个哨兵节点(dummy),dummy节点指向原链表的头结点。这样,当我们对头结点进行操作的时候就可以直接使用dummy节点,不用进行特判。
在对链表进行操作的时候 while的循环条件也是容易犯错的地方,我们不应该死记这题该是cur != null
还是cur.next != null
又或是其他。而是应该画个图,手动模拟一下,便知道结束的条件。
203.移除链表元素
题意:删除链表中等于给定值 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
输出:[]
思路
遍历列表找到要删除的节点的前一个节点,修改该节点的指针跳过要删除的节点。
关键在于,处理头结点和如何找到要删除的前一个节点。我们可以使用一个哨兵节点和pre指针来实现。
pre初始值为哨兵节点,cur初始值是头结点。这样每次pre和cur都向后移一位即可,判断如果cur等于要删除的节点就让pre = cur.next
,循环的条件为cur != null
。
代码
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
707.设计链表
题意:
在链表类中实现这些功能:
- get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
- addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
- addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
- deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
思路
本题不是一道算法题,是一道考察对链表的功能的具体实现的设计题。
熟悉链表具体操作即可,同样的我们引入哨兵节点和一个存储链表大小的size变量会方便我们的操作。
代码
class ListNode {
int val;
ListNode next;
ListNode(){}
ListNode(int val) {
this.val = val;
}
}
class MyLinkedList {
int size; // 链表长度
ListNode head; // 虚拟头结点
public MyLinkedList() {
size = 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) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) return;
if (index < 0) index = 0;
size ++;
ListNode pre = head;
// 包含一个虚拟头结点,所以要<=
for (int i = 0; i < index; i ++ ) {
pre = pre.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pre.next;
pre.next = toAdd;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return ;
size --;
if (index == 0) {
head = head.next;
return ;
}
ListNode pre = head;
for (int i = 0; i < index; i ++ ) {
pre = pre.next;
}
pre.next = pre.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
206.反转链表
题意:反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路
本题我们可以从题目要求入手,对链表进行一个模拟。不难看出我们需要将后一个节点指向前一个节点 ,在此基础上我们还要解决一个问题:我们以样例来说明,当我们将节点2指向节点1时,我们应该怎么移动当前指针到下一个节点。
显然,我们可以定义一个变量next来预先存储节点2的next指针即可。另一个问题是如何让节点1指向null,参考之前说过的操作引入一个哨兵节点,这样pre指针指向哨兵节点,cur指针指向头结点。在最开始我们就能让头节点指向null。
代码
1.双指针写法
class Solution {
public ListNode reverseList(ListNode head) {
// 复习,非递归写法
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
2.递归写法
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(head, null);
}
// 关于cur为什么为空 , 因为我们返回的是pre,如果cur == null 时 pre才指向最后一个链表的元素
public ListNode reverse(ListNode cur, ListNode pre) {
if (cur == null) return pre;
ListNode next = cur.next;
cur.next = pre;
return reverse(next, cur);
}
}
24. 两两交换链表中的节点
题意:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
思路
拿到一道题目我们看完题干和数据范围后,一定先自己动手模拟一下,理清楚题目要求,也能方便我们将模拟操作抽象为具体的代码。
下面是根据样例我们模拟的过程:
在图片中上面的链表是初始时的链表,下面的链表为我们的目标链表。
可以看出如果要得到目标链表我们必须得进行三个步骤:
- 将哨兵节点指向节点2
- 将节点2指向节点1
- 将节点1指向节点3
在我们完成上面三个步骤后,我们将当前指针移动两位,及如果我们要操作两个节点,指针必须在这两个节点的前面一个节点。
但是当我们在改变指向以后我们就不能找到节点1和节点3了,所以我们得提前存储一下节点1和节点3,由此可知循环的条件为cur.next != null && cur.next.next != null
根据以上思路不难写出代码。
代码
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
ListNode tmp = cur.next;
ListNode tmp1 = cur.next.next.next;
cur.next = cur.next.next;
cur.next.next = tmp;
cur.next.next.next = tmp1;
cur = cur.next.next;
}
return dummy.next;
}
}
19.删除链表的倒数第N个节点
题意:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例:
思路
首先,最暴力的思路就是遍历一遍统计链表长度,再遍历一遍删除倒数第N个节点,这种思路的代码实现简单,我们不在此给出。
我们考虑如何使用一趟扫描实现此功能,在这里我们引入一个快慢指针的思想。
我们设置两个指针他们的起点都为哨兵节点,其中快指针fast每次先移动n位,然后快慢指针才一起开始移动,当快指针到达链表末尾的时候,慢指针刚好指向我们要删除的倒数第N个节点的前一个节点。
如下图所示:
所以循环的结束条件为fast走到最后时,及cur.next != null
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while (n -- > 0) fast = fast.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
160.链表相交
题意:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
示例:图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:
示例 2:
示例 3:
思路
首先本题不是比较的val值相同,而是比较的节点相同,及val和next都相同。
明确了这一点之后我们继续讨论如何解决该问题,由于给出的两个链表可能长度并不相同,所以我们应该让两个链表从相同长度的位置开始进行比较。
所以我们先得到两个链表的长度,再让长的链表先前进两个链表之间的差值的距离。
这样我们就可以从相同位置开始进行比较,当比较到两个节点相同的时候,即找到了相交的节点返回即可,当循环结束时还没有找到则没有相交的节点。
while循环的条件不难得出为cur != null
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
int len;
while (curA != null) {
lenA ++;
curA = curA.next;
}
while (curB != null) {
lenB ++;
curB = curB.next;
}
// 找出长度大的那个链表
curA = headA;
curB = headB;
if (lenB > lenA) {
int tmp = lenA;
lenA = lenB;
lenB = tmp;
curA = headB;
curB = headA;
}
// 让长的先走
len = lenA - lenB;
while (len -- > 0) curA = curA.next;
while (curA != null) {
if (curA == curB) return curA;
curA = curA.next;
curB = curB.next;
}
return null;
}
}
142.环形链表II
题意:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
思路
首先要解决题目要求的问题,我们可以将其转换为解决两个子问题
子问题1:然后判断有环
在这里我们也引入一个快慢指针,快指针每次走两步,慢指针每次走一步。当链表中存在环的时候,快指针和慢指针一定会相遇。
子问题2:如何找到环的起点
根据子问题1得到的相遇的节点,我们用index表示,同时我们定义一个index1在头结点的位置,然后让两个节点一起走,当他们相遇的时候的节点即为环开始的节点。
具体证明请看:代码随想录
while 循环的条件为fast != null && fast.next != null
代码
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
ListNode idx = fast;
ListNode idx1 = head;
while (idx != idx1) {
idx = idx.next;
idx1 = idx1.next;
}
return idx;
}
}
return null;
}
}
标签:null,ListNode,cur,代码,随想录,next,链表,day1,节点
From: https://www.cnblogs.com/ku-man/p/17169329.html