链表

ListNode node = new ListNode();  //初始化一个空结点，无值（不提倡这样写）

ListNode node = new ListNode(0); //初始化一个节点值为0的空结点（最常用的规范写法）

// #include <bits/stdc++.h>
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    explicit ListNode(int x) : val(x), next(nullptr) {}
     // ListNode() : val(0), next(nullptr) {}
     // ListNode(int x) : val(x), next(nullptr) {}
     // ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr){
            return head;
        }
        else if(head->next == nullptr){
            return head;
        }
        ListNode* prev = nullptr;
        ListNode* curr;
        while(head != nullptr){
            curr = head;
            head = head->next;
            curr->next = prev;
            prev = curr;
        }
        return prev;
    }
};

int main(){
    ListNode n1(0);
    ListNode n2(2);
    ListNode n3(5);
    ListNode n4(7);
    ListNode n5(10);
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = &n5;
    ListNode* head = &n1;
    while(head){
        cout << head->val << ' ';
        head = head->next;
    }

    Solution so;
    so.reverseList(&n1);
    cout << endl;

    head = &n5;
    while(head){
        cout << head->val << ' ';
        head = head->next;
    }

    return 0;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
     ListNode *head = new ListNode(0);
     ListNode *p = head;

     while(l1 != NULL && l2 != NULL)
     {
         if(l1->val <= l2->val)
         {
             p -> next = l1;    //在新链表上插入值
             l1 = l1 -> next;   //原链表指针指向下一个
         }
         else
         {
             p -> next = l2;
             l2 = l2 -> next;
         }
         p = p -> next;
     }
     if(l1 != NULL)
         p -> next = l1;
     if(l2 != NULL)
         p -> next = l2;
     
     return head->next;
 }

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
       if (!list1) {
            return list2;
        } else if (!list2) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL) {}
};
 ListNode* reverseList(ListNode* head) {
        if(head == NULL)
            return NULL;
        ListNode *p0 = NULL;
        ListNode *p1 = head;
        ListNode *p2 = head->next;
        
        while(p1 != NULL)
        {
            p1 -> next = p0; //反转指向
            p0 = p1; //指针前进
            p1 = p2; //指针前进
            if(p2 != NULL)
                p2 = p2->next;
        }
        return p0;
    }

//另一种更简便的方法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t = pre->next;
            pre->next = cur; //指针翻转
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

ListNode* reverseList(ListNode* head) {
       if(head == NULL|| head->next == NULL)
           return head;
       ListNode *newhead = reverseList(head->next);//把新头结点递归到链表的最后一个元素，从后往前翻转。
       head->next->next = head;  //后一个结点指向前一个结点
       head->next = NULL;  //断了前一个结点指向后一个节点的关系
       return newhead;
}

ListNode* getKthFromEnd(ListNode* head, int k) {
      ListNode *p,*q;
      p = head, q = head;
      while(k--){
          p = p->next;
      }
      while(p){
          p = p->next;
          q = q->next;
      }
      return q;
   }