链表之增加头结点的前缀节点
- 在许多链表题中往往需要在题目给的头结点之前增加一个前缀节点
- 通常在删除链表和头结点需要交换时需要用到这一操作
- 因为增加这个节点就避免了对删除头结点这种特殊情况的特殊处理
- 而且往往在声明一个前缀节点之后再复制一个,前者保存不动用于最后结果返回,后者参与之后的操作
Leetcode203删除链表元素
- 给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。 - 输入:head = [1,2,6,3,4,5,6], val = 6
- 输出:head = [1,2,6,3,4,5,6], val = 6
public ListNode removeElements(ListNode head, int val) {
ListNode prefinalHead=new ListNode(-1,head);
ListNode preHead=prefinalHead;
while(head!=null){
if(head.val==val){
preHead.next=head.next;
}else{
preHead=preHead.next;
}
head=head.next;
}
return prefinalHead.next;
}
Leetcode24两两交换链表中的节点
- 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)
- 输入:head=[1,2,3,4]
- 输出:[2,1,4,3]
public ListNode swapPairs(ListNode head) {
if(head==null){//没元素
return null;
}
if(head.next==null){//只有一个元素
return head;
}
ListNode pre=head;
ListNode post=head.next;
ListNode finallastpre=new ListNode(-1,head);
ListNode lastpre=finallastpre;
while(pre!=null){
if(post==null){//最后只剩一个节点
pre=pre.next;
}else{
ListNode temp=post.next;
post.next=pre;
lastpre.next=post;
pre.next=temp;
lastpre=pre;
pre=pre.next;
if(temp!=null){
post=temp.next;
}else{
post=null;
}
}
}
return finallastpre.next;
}
Leetcode19删除链表的倒数第N个结点
- 给你一个链表,删除链表的倒数第
n
个结点,并且返回链表的头结点 - 输入:head=[1,2,3,4,5],n=2
- 输出:[1,2,3,5]
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode prefinalHead=new ListNode(-1,head);
ListNode preHead=prefinalHead;
ListNode fast=head;
ListNode slow=head;
for(int i=1;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
slow=slow.next;
fast=fast.next;
preHead=preHead.next;
}
preHead.next=slow.next;
return prefinalHead.next;
}