数据结构之链表复习
=====================================================================
链表类型的习题常用的技巧就是定义指针来代替 head 的，替 head 走，要么就是数学问题，环形链表就是利用数学思想取解决的，要么就是定义双指针来操作链表。
定义两个变量，一个使待删除的节点，一个为待删除节点的前驱节点，最后记得判断头节点是否为要删除的节点，最后返回头节点。
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
ListNode cur=head.next;
ListNode prev=head;
while(cur!=null){
if(cur.val==val){
prev.next=cur.next;
}else{
prev=cur;
}
cur=cur.next;
}
if(head.val==val){
head=head.next;
}
return head;
}
定义双指针法，类似于头插法，来将链表的节点头插法
cur 节点是待反转的节点 curNext 是保存下一个节点的地址值
1.先保存待反转节点下一个地址值，之后将头节点的 next 置空
2.只有用头插法将节点头插即可。
public ListNode reverseList(ListNode head) {
//三指针法来反转链表
if(head==null||head.next==null){
return head;
}
ListNode cur=head;//要头插的节点
ListNode curNext=head.next;//保存下一个节点的地址值
cur=curNext;
head.next=null;
while(cur!=null){
curNext=curNext.next;
cur.next=head;
head=cur;
cur=curNext;
}
return head;
}
定义快慢指针，注意偶数节点和奇数节点的情况
注意判断条件 在偶数情况下 如果是判断 fast.next.next 就会空指针异常，必须把判断条件两个都加上。
public ListNode middleNode(ListNode head) {
//定义快慢指针 快指针比慢指针多走一步 注意奇数和偶数情况
if(head==null||head.next==null){
return head;
}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
定义快慢指针 快指针先走 n-1 步 之后慢指针再走,修改地址值即可
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode dummy=new ListNode(0,head);
ListNode slow=dummy;
for(int i=1;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummy.next;
}
给定 X 值，分割链表 前面链表为小于 X 的值，后面链表为大于等于 X 的值
要考虑很多情况
1.第一次插入链表时 要将头节点和尾巴节点都指向插入的节点
2.不是第一次插入时，只需要把尾巴节点 next 值指向插入的节点，之后把尾巴节点往后挪
3.如果前面链表为空，返回后面链表的头
4。还需要将后面节点的 next 值置空，之后连接两个链表。
public ListNode partition(ListNode head, int x) {
//分割链表 将小于 x 的分为一部分，将大于等于 x 的分为一部分呢！ 乖乖 yy
if(head==null){
return null;
}
ListNode xh=null;//小于 x 的头节点
ListNode xe=null;;//小于 x 的尾巴节点
ListNode Xh=null;//大于等于 X 的头节点
ListNode Xe=null;//大于等于 X 的尾节点
ListNode cur=head;
while(cur!=null){
if(cur.val<x){
//小于 X 的部分
if(xh==null){
//第一次插入
xh=cur;
xe=cur;
}else{
//不是第一次插入
xe.next=cur;
xe=cur;
}
}else{
//>=X 的部分
if(Xh==null){
//第一次插入
Xh=cur;
Xe=cur;
}else{
//不是第一次插入
Xe.next=cur;
Xe=cur;
}
}
cur=cur.next;
}//判断 所有元素都大于 x 前面的链表没有数据 要返回后面的链表
if(xh==null){
return Xh;
}
xe.next=Xh;
if(Xh!=null){
//将最后一个元素置为 null
Xe.next=null;
}
return xh;
}
和合并有序数组是一样的，链表复杂一些要将后面节点地址先保存，之后定义傀儡节点，按照值小的顺序连接起
来
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//1.思路就是先定傀儡节点，将链表穿起来 定义两个变量将后面地址保存起来 之后串糖葫芦一样串起来
ListNode dummy=new ListNode(-1);
ListNode head=dummy;//保存傀儡节点
ListNode cur1=l1;//保存节点后面的地址值
ListNode cur2=l2;
while(l1!=null&&l2!=null){
cur1=l1.next;
cur2=l2.next;
if(l1.val<=l2.val){
dummy.next=l1;
l1=cur1;
}else{
dummy.next=l2;
l2=cur2;
}
dummy=dummy.next;
}
if(l1!=null){
dummy.next=l1;
}
if(l2!=null){
dummy.next=l2;
}
return head.next;
}
双指针 遇到相等的就跳过 ，最后要将最后一个节点置为空。
public ListNode deleteDuplicates(ListNode head) {
if(head==null){
return null;
}
ListNode prev=head;
ListNode cur=head.next;
while(cur!=null){
if(prev.val==cur.val){
cur=cur.next;
}else{
prev.next=cur;
prev=cur;
cur=cur.next;
}
}
prev.next=cur;
return head;
}
先用 set 判断是否存在 空间复杂度为 O（N），不太符合题目要求
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set=new HashSet<>();
while(head!=null){
set.add(head);
head=head.next;
if(set.contains(head)){
return true;
}
}
return false;
}
2.快慢指针数学问题，快指针走两步，慢指针走一步，有环一定相遇，没有环就不会相遇 空间复杂度为 O(1)
public boolean hasCycle(ListNode head) {
//快慢指针还是数学问题
if(head==null||head.next==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(slow!=fast){
if(fast==null||fast.next==null){
return false;
}
fast=fast.next.next;
slow=slow.next;
}
return true;
}
1.先利用 set 存储节点 之后循环判断，空间复杂度为 O（N）时间复杂度为 O（N），比较慢
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode>set=new HashSet<>();
while(headA!=null){
set.add(headA);
headA=headA.next;
}
while(headB!=null){
if(set.contains(headB)){
return headB;
}
headB=headB.next;
}
还未添加个人签名 2021.11.08 加入
还未添加个人简介
评论