2020.10.21每日复习

面试题02.03 删除中间节点在这里插入图片描述 **分析** 面试题02.02 返回倒数第k个节点在这里插入图片描述 **分析**

面试题02.03 删除中间节点

分析

因为只能访问该节点，故只知道该节点及其之后的节点，并不知道之前的节点信息。令当前节点的值和指向都等于该节点下一节点的值和指向，即相等于用下一节点覆盖了当前节点。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public void deleteNode(ListNode node) { node.val = node.next.val;//下一节点的值赋给当前的节点 node.next = node.next.next;//下一节点的指针域给当前节点，相当于当前节点直接跳过下一节点，指向下下节点 } }

---

面试题02.02 返回倒数第k个节点

分析

用两个指针，一个指针指向距离首节点k处的节点，再将两个指针同时向后移动，当后指针指向最后一个节点的下一个节点-----空节点时，前指针指向的节点就是倒数第k个节点。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int kthToLast(ListNode head, int k) { ListNode colon = head; for(int i = 0; i < k; i++) { colon = colon.next; } while(colon != null) { head = head.next; colon = colon.next; } return head.val; } }