问题2
问题3
题目来源:https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/
实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
题解3 - I
空间复杂度O(n) 时间复杂度O(n)
链表相对于vector或者array,你不知道当前有多少个元素。如果我知道有多少个元素,并且能用下标访问,那么我肯定可以直接通过
k来访问对应的元素。因此我可以遍历一遍链表,赋值到vector里面,然后用下标访问倒数k元素的引用最后返回
c++:
class Solution {
public:
int kthToLast(ListNode* head, int k) {
vector<decltype(head->val)> array;
int size = 0;
while(head != NULL){
array.push_back(head->val);
size += 1;
head = head->next;
}
return array[size - k];
}
};
python:
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
array = []
size = 0
while(head != None):
array.append(head.val);
size += 1;
head = head.next;
return array[size - k];
题解3 - II
空间复杂度O(1) 时间复杂度O(n)
相对于题解1,这个题换了一个思路,设想,我可以有两个指针,指针p1指向头部,指针p2与p1距离为k-1
那么我同时让p1,p2移动到下一个节点,知道p2是尾部节点,那么p1肯定是倒数第k个节点。
c++:
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode * pstart = head;
for(int i = 1 ; i < k ; i ++){
pstart = pstart->next;
}
while (pstart->next != NULL){
pstart = pstart->next;
head = head->next;
}
return head->val;
}
python:
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
pstart = ListNode(head.val)
pstart.next = head.next
for i in range(1,k):
pstart = pstart.next
while pstart.next != None :
pstart = pstart.next
head = head.next;
return head.val
问题4
题目来源: https://leetcode-cn.com/problems/delete-middle-node-lcci/
实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
(注意,这里的输入,不是链表的表头,而是要删除的那个节点)
题解4
空间复杂度O(1) 时间复杂度O(1)
注意到,因为我的输入是要删除的那个节点,而我不知道这个节点的父节点是什么,
因此我只能让要被删除的那个节点,模拟成下一个节点,然后删除下一个节点,从而实现这个链表删除这个节点
即,我让输入节点的值变成下一个节点的值,然后让输入节点的next指向下下个节点即可。
C++:
class Solution {
public:
void deleteNode(ListNode * node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
python:
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next