链表 | dhx

18.删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

定义一个next 为 head 的指针，用来过需要删除的节点是第一个节点的情况，对于别的位置，直接遍历即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
        public ListNode deleteNode(ListNode head, int val) {
            if(head.next==null) return null;
            ListNode t=new ListNode(1);
            t.next=head;
            while(t.next!=null){
                if(t.next.val==val){
                    if(t.next.val== head.val){
                        return head.next;
                    }
                    if(t.next.next!=null)
                    {
                        t.next=t.next.next;
                    }
                    else t.next=null;
                    return head;
                }
                t=t.next;
            }
            return head;
        }
}

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

双指针

定义两个指针， p1先不动，p2 先遍历 n个节点，使得p1 与 p2 相差 N-1个节点，

然后让p1,p2一起移动，直到p2指向链表末尾的节点，此时p1的下一个节点就是需要删除的节点，然后

通过改变指向来删除元素即可，如果需要删除的元素是头结点此时会有 p1.next=head; , 直接另res=null; 然后返回p1.next.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 removeNthFromEnd(ListNode head, int n) {
        if(head.next==null) return null;
        ListNode res=head;
        ListNode p1=new ListNode(1,head);
        ListNode p2=new ListNode(2,head);
        for(int i=0;i<n;i++){ 
// 应该让 p1 最后处于要删除的元素的前一个，然后调用next 删除,p1与p2相隔n-1个元素, 需要让p2提前走n步
            p2=p2.next;
        }
        while(p2.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        if(p1.next==head) // 判断p1 是否移动了， 如果没有移动，说明要删除的是头结点
            res=null;
        p1.next=p1.next.next;
        return res==null?p1.next:res;
    }
}

@Test

@Test
public void TestNull()
{
    ListNode l2 =new ListNode(10);
    ListNode l1=new ListNode(9,l2);
    ListNode res=l1;
    res=null;
    System.out.println(l1);
}