问题1

设计算法，将带头结点的单链表原地反转，原地是指辅助空间复杂度为O(1)。

题解1

时间复杂度: O(n) 空间复杂度 O(1)
因为链表，如果你把第i+1个节点的 next值，设置为第i个节点，那么你就丢掉了第i+2个节点，因此我需要三个变量，时刻保存这三个节点。
c++:

  1. #include <iostream>
  2. using namespace std;
  3. struct Node {
  4.     int val;
  5.     Node * next = nullptr;
  6. };
  7. Node *  reverse(Node * head){
  8.     Node * next = head->next;
  9.     head->next = nullptr;
  10.     while(next != nullptr){
  11.         Node  * next_next = next->next;
  12.         next->next = head;
  13.         head = next;
  14.         next = next_next;
  15.     }
  16.     return head;
  17. }
  18. void print_List(Node * head){
  19.     while (head != nullptr){
  20.         cout << head->val << " ";
  21.         head = head->next;
  22.     }
  23.     cout << endl;
  24. }
  25. int main() {
  26.     //首先生成一个列表
  27.     Node nodes [10];
  28.     for(int i = 0;i < 10 ; i ++){
  29.         nodes[i] = Node{i};
  30.     }
  31.     for(int i = 1;i < 10;i ++){
  32.         nodes[i - 1].next = & nodes[i];
  33.     }
  34.     //打印列表
  35.     print_List(& nodes[0]);
  36.     //反转
  37.     auto new_head = reverse(&nodes[0]);
  38.     //再次打印
  39.     print_List(new_head);
  40. }

python:

class Node:
    def __init__(self,val : int, next = None):
        self.val = val
        self.next = next


def Reverse(head : Node) -> Node:
    '''
    输入头结点,逆转列表,返回尾结点,也就是新的头结点
    :param head:
    :return:
    '''
    next= head.next     #记录下当前操作的节点的下一个节点
    head.next = None    #因为头结点是翻转后的尾结点,因此尾结点next是None 因此把head.next 设置为None
    while next != None:
        next_next = next.next  #记录下一个节点的下一个节点
        next.next = head #让下一个节点指向当前操作的
        head = next #让当前操作的节点变成下一个
        next = next_next # 更新next的值

    return head

def Print_Listnodes(head : Node):
    '''
    打印链表
    :param head:
    :return:
    '''
    while head != None:
        print(head.val,end=" ")
        head = head.next
    print()

if __name__ == "__main__":

    #新建一个链表
    head = Node(0)
    p = head
    for i in range(1,10):
        new_node = Node(i)
        p.next = new_node
        p = new_node

    #打印链表
    Print_Listnodes(head)

    #反转链表并获得新头
    new_head = Reverse(head)

    #打印反转后的
    Print_Listnodes(new_head)

问题2

设计一个算法，判断一个链表是否有环，如果有，找出环的入口点并返回，否则返回NULL。链表结构可如下考虑：

题解2

时间复杂度O(n) 空间复杂度O(1)

#include <iostream>
using namespace std;
struct Node {
    int val;
    Node * next = nullptr;
};
Node *  FindLoopStart(Node  * head){
      Node * slow = head, *fast = head;
      while (fast != nullptr){
          slow = slow->next;
          fast = fast->next->next;
          if (slow == fast)
              break;
      }
      if(fast == nullptr)
          return nullptr;
      Node * root = head;
      while (root != slow){
          root = root->next;
          slow = slow->next;
      }
      return root;
}
void print_List(Node * head){
    while (head != nullptr){
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
int main() {
    Node nodes [10];
    //构建一个带环的列表 大概就是 0->1->2->3->....->9 ->0
    for(int i = 0;i < 10 ; i ++){
        nodes[i] = Node{i};
    }
    for(int i = 1;i < 10;i ++){
        nodes[i - 1].next = & nodes[i];
    }
    //nodes[9].next = &nodes[5];
    //找到环的入口
    auto new_head = FindLoopStart(&nodes[0]);
    //输出环入口值
    if (new_head != nullptr)
        cout << new_head->val;
    else
        cout << "No loop in the list";
}

问题3

题目来源:https://leetcode-cn.com/problems/remove-duplicate-node-lcci/
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点

题解3

时间复杂度O(n),空间复杂度O(1)
即开设一个很大的数组,用来保存元素值是否访问过
c++ : 

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if( head == nullptr) return head;
        bool valexist[20001] = {};
        ListNode * previous_node = head;
        ListNode * in_hand_node  = head->next;
        valexist[head->val] = true;
        while (in_hand_node != nullptr){
            if(valexist[in_hand_node->val]){
                //表明出现过这个值,移除这个节点
                previous_node->next = in_hand_node->next;
            }
            else{
                //没有出现过这个值,记录这个节点
                valexist[in_hand_node->val] = true;
                previous_node = in_hand_node;
            }
            in_hand_node  = in_hand_node->next;
        }
        return head;
    }
};

image.png
python:

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        valexisted = [False] * 20001
        if head == None: return None
        previous_node = head
        assert id(previous_node) != id(head)
        valexisted[previous_node.val] = True
        in_hand_node =  head.next
        while in_hand_node != None:
            if valexisted[in_hand_node.val]:
                previous_node.next = in_hand_node.next
            else:
                valexisted[in_hand_node.val] = True
                previous_node = in_hand_node
            in_hand_node = in_hand_node.next
        return head

image.png