本文主要是介绍LeetCode100.删除链表的倒数第 N 个结点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1. 题目大意
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
2. 思路分析
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
我们可以先遍历一遍链表求出链表的长度,再遍历时遇到倒数第n+1个,可以直接删除第n个。
接下来是进阶,上面的方法需要遍历两遍链表,如果遍历一次那?答:使用双指针,A指针在原地,另一个B指针距离上一个指针N个节点,当B指针为空的时,A指针恰好指向第N个节点。当然为了方便删除的操作,可以在列表前面加一个头节点,A从头节点开始计算,这样当B节点为空的时候,A恰好指向倒数第N个节点的前一个节点。
3. 代码示例
Java版本
/*** 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 = head;int size = 0;while(temp!=null){temp = temp.next;size++;}if(size ==1){return null;}ListNode dummy = new ListNode(0, head);ListNode cur = dummy;for(int i=1; i<size-n+1; i++){cur = cur.next;}cur.next = cur.next.next;return dummy.next;}
}
Python版本
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:res = ListNode(0)cur = res# 保存进制记录carry = 0while l1 is not None or l2 is not None or carry:x = 0 if l1 is None else l1.valy = 0 if l2 is None else l2.valsum = x+y+carrycarry = sum // 10sum = sum % 10cur.next = ListNode(sum)cur = cur.nextif l1 is not None:l1 = l1.nextif l2 is not None:l2 = l2.nextreturn res.next
这篇关于LeetCode100.删除链表的倒数第 N 个结点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!