题目:力扣https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
/** * 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) { ListNode temp = new ListNode(0, head); int length = getLength(head); ListNode cur = temp; for (int i=1;i<length-n+1;i++) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = temp.next; return ans; } public int getLength(ListNode head) { int length = 0; while (head!=null) { head = head.next; length++; } return length; } }
思路:先计算传入的head链表有多长,然后使cur去到指定的倒数位置,然后将要删去结点的头和尾的结点直接相连,用ans指向操作后的链表,最后返回ans即可。
1.先写一个获取链表长度的数组getLength()。遍历链表,然后用length记录长度,最后返回length。
public int getLength(ListNode head) { int length = 0; while (head!=null) { head = head.next; length++; } }
2. 准备工作。声明一个temp和一个cur,temp是指向传入链表的头结点,而cur是指向需要操作的结点。计算传入链表长度需要调用getLength()方法。
ListNode temp = new ListNode(0, head); int length = getLength(head); ListNode cur = temp;
3.用循环将cur移动到指定位置(需要删除结点的上一个结点)。将cur.next的值修改成需要删除的结点的下一个结点的值。用ans指向完成删除操作的链表temp.next(需要.next是因为temp有头结点,头结点不需要返回,因此从头结点的下一个结点开始。)最后返回ans即可。
for (int i=1;i<length-n+1;i++) { cur = cur.next; } cur.next = cur.next.next; ListNode ans = temp.next; return ans; }