一.链表的基础结构

  class ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

1.1 尾部添加节点

void AddNode(ListNode** head, int value){            //ListNode* head为啥不行
    ListNode* new_node=new ListNode(value);               //先new一个新节点

    if (*head == NULL){
       *head=new_node;
    }else{
       ListNode* tmp=*head;
       while(tmp->next!=NULL){
           tmp=tmp->next;
       }
       tmp->next=new_node;
   }
}

二. Easy 题目

2.1 剑指 Offer 06. 从尾到头打印链表

• 不能改变链表的结构
• 倒序想到栈和递归

2.1.1 栈

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> result;
        if(head ==NULL)
            return result;

        stack<int> tmp;
        while(head!=NULL){
            tmp.push(head->val);
            head=head->next;
        }
        while(tmp.size()){
            result.push_back(tmp.top());
            tmp.pop();
        }
        return result;
    }
};

注意

• 返回值有类型的话，不能返回NULL。

2.1.2 递归

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> result;
        if(head==NULL)
            return result;
        reverseList(head,result);
        return result;
    }

    void reverseList(ListNode* head, vector<int> & result) {
        if(head==NULL)
            return;
        if(head->next!=NULL){
            reverseList(head->next,result);
        }
        result.push_back(head->val);
    }
};

注意

• 递归可能导致函数调用栈溢出，栈的鲁棒性更好些。
• 错误解法：对递归概念不够熟悉。

        if(head->next!=NULL){
            reverseList(head->next,result);
        }else{
        result.push_back(head->val);
       }

2.2 剑指 Offer 22. 链表中倒数第k个节点

类似题目： 面试题 02.02. 返回倒数第 k 个节点

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if(head ==NULL || k==0) return NULL;            //k==0一开始没想到，注意
        ListNode* pre=head;
        while(--k){
            if(pre->next != NULL){
                pre=pre->next;
            }else{
                return NULL;
            }
        }
        ListNode* aft=head;
        while(pre->next!=NULL){
            pre=pre->next;
            aft=aft->next;
        }
        return aft;
    }
};

注意

• 习惯于k++, k值已知时，k--更优。k--和--k注意区分。
• 需要增加k是否等于0的判断。

2.3 剑指 Offer 24. 反转链表

• 做了很多次反转链表的题，但是没有详细的记下思路。
• 反转顺序：先按照pre, node, next获取最初状态。然后以中间节点node为基准，改变指针方向。最后再以pre, node, next的顺序获取新的节点。
• node不为空就可以继续翻转。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next ==NULL)
            return NULL;
        ListNode* pre=NULL;
        ListNode* node=head;
        ListNode* new_head=NULL;

        while(node!=NULL){
            ListNode* after=node->next;
            if(after ==NULL)
               new_head=node;

           node->next=pre;

           pre=node;
           node=after;
        }
        return new_head;
    }
};

2.4 21. 合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL)
           return l2;
        if(l2 ==NULL)
           return l1;
        ListNode* new_head=new ListNode();
        if(l1->val < l2->val){
          new_head->val=l1->val;
          l1=l1->next;
        }else{
          new_head->val=l2->val;
          l2=l2->next;            
        }
        ListNode* node=new_head;
        while(l1!=NULL && l2 !=NULL){
            if(l1->val < l2->val){
                node->next=new ListNode(l1->val);
                node=node->next;
                l1=l1->next;
            }else{
                node->next=new ListNode(l2->val);
                node=node->next;
                l2=l2->next;            
            }
        }
        node->next=l1!=NULL? l1:l2;
        return new_head;
    }
};

注意：更高效版本

• 可以设置一个假的头结点，将头结点操作和后面节点的操作结合起来。
• 判断l1, l2是否为空，使用break的话更高效。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* fake_head=new ListNode(-1);
        ListNode* node=fake_head;
        while(l1!=NULL && l2 !=NULL){
            if(l1->val < l2->val){
                node->next=new ListNode(l1->val);                
                l1=l1->next;
            }else{
                node->next=new ListNode(l2->val);
                l2=l2->next;            
            }
            node=node->next;                              //相同代码部分提出来，更高效。
        }
        node->next=l1!=NULL? l1:l2;
        return fake_head->next;
    }
};

还可以使用递归方法

三. Medium题目

3.1 剑指 Offer 35. 复杂链表的复制

• 第一种方法先复制一遍链表，对着原来的列表复制指向信息，每个列表结点都需要遍历寻找，O(n^2).
• 第二种 用哈希表实现节点遍历。空间换时间能降到O(n)。
• 第三种 不用辅助空间的情况下，O(n)时间复杂度。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) 
          return NULL;
        copyList(head);
        copyRandom(head);
        return splitList(head);
    }

    void copyList(Node* head) {
        Node* node=head;
        while(node){
            Node* new_node=new Node(node->val);
            new_node->next=node->next; 
            node->next=new_node;
            node=new_node->next;
        }
    }

    void copyRandom(Node* head) {
        while(head){
            if(head->random)
                head->next->random=head->random->next;
            head=head->next->next;
        }
    }

    Node* splitList(Node* head){
        Node* new_head=head->next;
        
        while(head!=NULL){
            Node* next_node=head->next;
            if(next_node)
                head->next=next_node->next;
            else
                head->next=NULL;
            head=next_node;
        }
        return new_head;
    }
};