问题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++:

  1. class Solution {
  2. public:
  3. int kthToLast(ListNode* head, int k) {
  4. vector<decltype(head->val)> array;
  5. int size = 0;
  6. while(head != NULL){
  7. array.push_back(head->val);
  8. size += 1;
  9. head = head->next;
  10. }
  11. return array[size - k];
  12. }
  13. };

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