锐客网

  1. 首页 > it技术 > >

Leetcode刷题之链表增加头结点的前缀节点

链表之增加头结点的前缀节点

  • 在许多链表题中往往需要在题目给的头结点之前增加一个前缀节点
  • 通常在删除链表和头结点需要交换时需要用到这一操作
  • 因为增加这个节点就避免了对删除头结点这种特殊情况的特殊处理
  • 而且往往在声明一个前缀节点之后再复制一个，前者保存不动用于最后结果返回，后者参与之后的操作
? 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; }

【Leetcode刷题之链表增加头结点的前缀节点】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

    推荐阅读


    上一篇：CommonCollection1反序列化学系

    下一篇：java的枚举