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; 
    }
  

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;
    }