[数据结构与算法]剑指Offer - 12_删除链表的节点

题目描述

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

示例

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为?5?的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

思路

1. 定义两个指针，一个为前驱结点，一个为真正要遍历和判断的结点
2. 如果找到相等的，直接让前驱结点的下一个结点指向当前遍历节点的下一个结点即可
3. 最后返回头结点

Code

public class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (null == head) {
            return null;
        }
        //如果头结点是，直接返回
        if (val == head.val) {
            return head.next;
        }
        //前驱结点
        ListNode preNode = head;
        //后继结点
        ListNode nextNode = head.next;
        //循环遍历
        while (null != nextNode && val != nextNode.val) {
            //不是，则指向下一个结点
            preNode = nextNode;
            nextNode = nextNode.next;
        }
        //nextNode不是null则表示找到相同的值
        if (null == nextNode) {
            return null;
        }
        //nextNode结点处的值和目标值相等，则让preNode的下一个结点直接指向nextNode的下一个结点
        preNode.next = nextNode.next;
        return head;
    }
}