算法刷题记录-链表移除元素
移除链表元素
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == 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
输出:[]
思路:就是链表移除元素,每次找到就将p.next移到q.next。
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return head;
}
if(head.val==val & head.next==null){
return null;
}
while (head.val==val){
head=head.next;
if(head==null){
return head;
}
}
ListNode p=head;
ListNode q=p.next;
while (q!=null){
if(q.val==val){
p.next=q.next;
q=p.next;
}
else {
p=p.next;
q=q.next;
}
}
return head;
}
设计链表
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性 prev
以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList
类:
MyLinkedList()
初始化MyLinkedList
对象。int get(int index)
获取链表中下标为index
的节点的值。如果下标无效,则返回-1
。void addAtHead(int val)
将一个值为val
的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)
将一个值为val
的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)
将一个值为val
的节点插入到链表中下标为index
的节点之前。如果index
等于链表的长度,那么该节点会被追加到链表的末尾。如果index
比长度更大,该节点将 不会插入 到链表中。void deleteAtIndex(int index)
如果下标有效,则删除链表中下标为index
的节点。
思路:就是麻烦了点,其实就是链表正常的操作
class MyLinkedList {
ListNode head;
int len=0;
public MyLinkedList() {
}
public int get(int index) {
if(head==null)return -1;
if(index<0)return -1;
if(index>=len)return -1;
int indextemp=0;
ListNode p=head;
while (indextemp!=index){
p=p.next;
indextemp++;
}
return p.val;
}
public void addAtHead(int val) {
if(head==null){
head=new ListNode(val);
len++;
}
else {
ListNode node=new ListNode(val);
node.next=head;
head=node;
len++;
}
}
public void addAtTail(int val) {
if(head==null) {
head=new ListNode(val);
len++;
}
else {
ListNode p=head;
while (p.next!=null){
p=p.next;
}
p.next=new ListNode(val);
len++;
}
}
public void addAtIndex(int index, int val) {
if(index>len){
return;
}
else if(head==null & index==0){
head=new ListNode(val);
return;
}
else if(index==0){
ListNode p=new ListNode(val);
p.next=head;
head=p;
len++;
return;
}
int indextemp=1;
ListNode p=head;
while (p.next!=null){
if(index==indextemp)break;
p=p.next;
indextemp+=1;
}
if(p.next==null){
p.next=new ListNode(val);
len++;
}
else {
ListNode q=new ListNode(val);
q.next=p.next;
p.next=q;
len++;
}
}
public void deleteAtIndex(int index) {
if(head==null)return;
if(index<0)return;
if(index>=len)return;
if(index==0){
head=head.next;
len--;
}
else {
int indextemp=1;
ListNode p=head;
while (indextemp!=index){
p=p.next;
indextemp+=1;
}
p.next=p.next.next;
len--;
}
}
}
class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
反转链表
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
思路:遍历链表,头插节点
public ListNode reverseList(ListNode head) {
if(head==null)return head;
ListNode tail=new ListNode(head.val);
ListNode head1=new ListNode();
head=head.next;
while (head!=null){
head1=new ListNode();
head1.val=head.val;
head1.next=tail;
tail=head1;
head=head.next;
}
return tail;
}
两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
思路:三个指针,分别指向交换的两个元素,这两个元素的前一个元素交换代码为:
p.next=q.next;
q.next=p;
pre.next=q;
更新的代码为:
pre=pre.next.next;
p=p.next;
if(p!=null)q=p.next;
else q=null;
完整代码如下:
public ListNode swapPairs(ListNode head) {
ListNode p=head;
if(p==null)return head;
ListNode q=p.next;
if(q==null)return head;
p.next=q.next;
q.next=p;head=q;
ListNode pre=head.next;
p=p.next;
if(p!=null)q=p.next;
else q=null;
while (q!=null){
p.next=q.next;
q.next=p;
pre.next=q;
pre=pre.next.next;
p=p.next;
if(p!=null)q=p.next;
else q=null;
}
return head;
}
删除链表倒数第n个节点
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
思路:暴力解法没什么好说的,两趟循环解决,第一个循环确定链表长度,第二个循环删除。代码如下:
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head.next==null & n==1)return null;
ListNode p=head;int len=0;
while (p!=null){
p=p.next;len++;
}
if(n==len){
head=head.next;
return head;
}
int index=1;p=head;
while (index!=len-n){
p=p.next;
index++;
}
p.next=p.next.next;
return head;
}
一趟循环解决:
用一个字典存储每个节点索引,最后将len-n的节点后一个节点删了即可,但是不知道为什么时间复杂度不准。
public ListNode removeNthFromEnd(ListNode head, int n) {
HashMap<Integer,ListNode> map=new HashMap<Integer,ListNode>();
if(head.next==null & n==1)return null;
ListNode p=head;int len=0;
while (p!=null){
map.put(len+1,p);
p=p.next;len++;
}
if(n==len){
head=head.next;
return head;
}
ListNode pre=map.get(len-n);
pre.next=pre.next.next;
return head;
}
链表相交
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。
思路:这题的意思是,两个已经定义好的链表,可能会有交点,找到这个交点。暴力解法就是一个二重循环:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p=headA;
ListNode q=headB;
while (q!=null){
p=headA;
while (p!=null) {
if (p == q) {
return p;
}
p = p.next;
}
q=q.next;
}
return null;
}
解法二:开了个字典,空间换时间
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashMap<ListNode,Integer> map=new HashMap<>();
ListNode p=headA;ListNode q=headB;
int len=0;
while (p!=null){
map.put(p,len);
p=p.next;
len++;
}
while (q!=null){
if(map.containsKey(q))return q;
q=q.next;
}
return null;
}
环形链表
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
思路:一样的,用一个字典存起来就行了
public ListNode detectCycle(ListNode head) {
HashMap<ListNode,Integer> map=new HashMap<>();
ListNode p=head;
if(p==null || p.next==null)return null;
while (p!=null){
if(map.containsKey(p))return p;
else {
map.put(p,0);
p=p.next;
}
}
return null;
}
标签:head,ListNode,val,next,链表,移除,null,刷题
From: https://www.cnblogs.com/hfutxcj/p/17830221.html