7月8日 四道经典单链表oj题
大家好呀,本博客目的在于记录暑假学习打卡,后续会整理成一个专栏,主要打算在暑假学习完数据结构,因此会发一些相关的数据结构实现的博客和一些刷的题,个人学习使用,也希望大家多多支持,有不足之处也请指出,谢谢大家。
一,203.移除链表元素
方法一:定义新链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null)
return head;
ListNode newtail = head;
ListNode newhead = new ListNode();
ListNode cur = newhead;
while (newtail != null) {
if (newtail.val != val) {
cur.next = newtail;
cur = newtail;
newtail = newtail.next;
} else {
if (newtail.next == null)
cur.next = null;
newtail = newtail.next;
}
}
return newhead.next;
}
}
方法二:在原链表基础上删除
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null)
return head;
ListNode prev = head;
ListNode pcur = head.next;
while (pcur != null) {
if (pcur.val == val) {
prev.next = pcur.next;
pcur = pcur.next;
} else {
prev = pcur;
pcur = pcur.next;
}
}
if(head.val==val)
head=head.next;
return head;
}
}
二,206.反转链表
采用了把后面的节点头插到头节点前面的方式
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null)
return head;
ListNode cur = head.next;
head.next = null;
ListNode curN;
while (cur != null) {
curN = cur.next;
cur.next = head;
head = cur;
cur = curN;
}
return head;
}
}
三,876链表的中间节点
运用了快慢指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null)
return head;
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null)
{
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}
四,面试题02.02 返回倒数第k个节点
采用快慢指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int kthToLast(ListNode head, int k) {
if(head==null)
return -1;
ListNode fast=head;
ListNode slow=head;
int count=0;
while(count!=k-1){
fast=fast.next;
count++;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow.val;
}
}
本期博客就到这里,感谢阅读
原文地址:https://blog.csdn.net/2302_81982408/article/details/140271934
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!