剑指 Offer 18. 删除链表的节点

题目

剑指 Offer 18. 删除链表的节点

我的复述：
假如有一个链表是4->1->5->9，指定删除节点5，那么返回新的链表为4->1->9。

题解

双指针

• 定义pre和cur两个指针
• 当cur指向要删除的节点时，让pre直接指向cur指针的下一个节点即可

//Java
/**
 * 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.val == val) return head.next;
        //设置两个指针，一个指针指向当前的节点
        ListNode pre = head;
        //一个指针指向当前节点的下一个节点
        ListNode cur = head.next;
        //当cur为空或cur节点值等于val时跳出循环
        while (cur != null && cur.val != val) {
            //两个指针不断的向前移动
            //pre来到cur的位置
            pre = cur;
            //cur来到下一个节点位置
            cur = cur.next;
        }
        //相当于覆盖掉了cur的节点值
        pre.next = cur.next;
        //最后返回链表头结点即可
        return head;
    }
}

leetcode-cn执行用时：

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.8 MB, 在所有 Java 提交中击败了63.11%的用户

//Go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(head *ListNode, val int) *ListNode {
    //特殊情况处理，删除的节点是头结点时
    if head.Val == val {
        return head.Next
    }
    //设置两个指针，一个指针指向当前的节点
    pre := head
    //一个指针指向当前节点的下一个节点
    cur := head.Next
    //当cur为空或cur节点值等于val时跳出循环
    for cur != nil && cur.Val != val {
        //两个指针不断的向前移动
        //pre来到cur的位置
        pre = cur
        //cur来到下一个节点位置
        cur = cur.Next
    }
    //删除指定节点
    pre.Next = cur.Next
    //最后返回链表头结点即可
    return head
}

leetcode-cn双百通过：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了100.00%的用户