Single Linked List

相比較另一個基本的數(shù)據(jù)結(jié)構(gòu)array，linked list有幾個優(yōu)勢：尺寸是可以動態(tài)分配韭脊，insert或者delete更加方便童谒。缺點就是不可以ramdom access，并且在結(jié)構(gòu)中需要分配額外空間來指示下一個pointer沪羔。

基本操作

作為data strucutre里面基本的數(shù)據(jù)結(jié)構(gòu)Linked list有很多特殊的性質(zhì)值得我們?nèi)プ⒁?由于它是線性結(jié)構(gòu)大多數(shù)linked list問題還是相對其他數(shù)據(jù)結(jié)構(gòu)（如tree, graph)較容易的饥伊。由于Linked List是由一個個節(jié)點(node)相聯(lián)組成的,因此首先看一下一個node一般怎么寫吧（這里主要先討論的單向的鏈表，雙向鏈表或者其他變種會在之后章節(jié)討論）：

struct Node{
       int val;
       Node *next;
       Node(int x) : val(x), next(nullptr){}
  }

從以上可以看出在c++中Node一般是用struct來生成蔫饰，并且可以使用constructor來初始化Node琅豆，因此初始化node就跟普通的class一樣。了解了Node的結(jié)構(gòu)之后篓吁，下面就看看怎樣insert, delete one node on the linked list.
首先來看insertion, 我們需要考慮兩種情況：1：如果原來的linked list是空的茫因，insert需要更新第一個node(header),一般linked list由the first node (header)來表示，一旦有了第一個node的地址其他操作都可以從這里進行; 2：如果原來的linked list是非空杖剪，insert需要更新previous node和next node的聯(lián)結(jié)關(guān)系冻押。在這里我們來介紹一個小技巧，對于第一個node需要update的情形（即linked list可能空的）盛嘿，一般可以使用dummy node來避免使用if來分情況討論洛巢，具體方法就是建立一個dummy node使得它next指向linked list的第一個node,但是需要注意的是此時函數(shù)返回值必須為Node *即pointer to Node.因此在函數(shù)的signature給定的情況下，可以寫一個wrapper函數(shù)在wrapper function中call這個函數(shù)來完成孩擂。以下是具體的insertion函數(shù)狼渊，注意這里返回Node pointer指向header,這里插入的位置是插入節(jié)點的值大于前一個節(jié)點并且小于后一個節(jié)點箱熬。

Node * insert(Node *node, Node *top){
  Node dummy(-1);
  dummy.next = top;
  if(top == nullptr){
     dummy.next = node;
     return dummy.next;
   }
 
Node *prev = &dummy, *cur = prev->next;
 while(cur->val < node->val && cur){
          prev = cur;
          cur = cur ->next;
    }
 
 if(cur == nullptr){
    prev->next = node;
  }else{
    Node *next = cur->next;
    prev->next = node;
    node->next = next;
 }

 return dummy.next;
}

其實這里可以修改一下prev和cur的起始位置（即向前在移一位）类垦，這樣可以避免討論head節(jié)點是否為空。并且需要注意此時dummy node的初始化值需要改為INT_MIN：

 Node *insert(Node *node, Node *top){
    Node dummy(INT_MIN);
    dummy.next = top;
    Node *prev = nullptr, cur = &dummy;
    while(cur && cur ->val < node->val){
           prev = cur;
           cur = cur->next;
      }
     prev->next = node;
     node->next = cur;
  return dummy.next;
 }

這里需要注意while里面首先判斷cur是否存在城须，再比較cur-val和node->val。

對應(yīng)insertion的就是delete了，這里同樣還是用dummy node的方法來解決臼疫，這里刪除的是節(jié)點值等于key的所有節(jié)點仰坦，需要注意的是得一直跟蹤記錄需要刪除的前一個node:
Remove Linked List Elements

void delete(Node *head, int key){
  Node dummy(-1);
  dummy.next = head;
  Node *prev = &dummy, *cur= dummy.next;
  while(cur){
    if(cur->val == key){
       Node *tmp = cur;
       prev->next = cur->next;
       delete tmp;
     }else{
       prev = prev->next;
     }
      cur = prev->next;
    }
 }

以上的方法是通過改變前后的節(jié)點關(guān)系，然后刪除節(jié)點的方法特別注意刪除節(jié)點之后前驅(qū)節(jié)點不需要更新。另外注意prev和cur兩個指針需要同步更新陪汽， 如果給定要刪除的節(jié)點训唱，可以通過copy value的方法來刪除節(jié)點：

void delete(Node *n){
      if(n->next){
        n->val= n->next->val;
        Node *tmp = n->next;
        n->next = n->next->next;
        delete tmp;
       }else{
           Node *tmp = n;
           n = nullptr;
           delete tmp;
        }
    }         

這里需要注意討論下一個節(jié)點是否是空的，然后分情況進行處理挚冤。類似的方法况增，刪除整個linked lis如下(不需要dummy node)：

 void delete(Node * head){
       Node *cur = head;
         while(cur){
             Node *tmp = cur;
             cur = cur->next;
             delete tmp;
          }
     }

經(jīng)典的刪除問題: 刪除重復(fù)的節(jié)點

ListNode *deleteDuplicates(ListNode *head){
      if(head == nullptr)
          return head;
      ListNode dummy(-1);
      dummy.next = head;
      ListNode *cur = head;
      while(cur){
           while(cur->next && cur->next->val == cur->val){
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
             }
          cur = cur->next;
      }
     return dummy.next;
 }

這里需要注意一個地方在while循環(huán)里面判斷是否有重復(fù)節(jié)點時用的是while而并非if,如果采用if就會導(dǎo)致重復(fù)節(jié)點超過兩個沒辦法刪除。雖然這里采用兩個loop相互嵌套训挡，實際上running time還是線性的澳骤，其實這道題不需要dummy node而且也不需要兩個循環(huán)嵌套，更改程序如下：

  ListNode *deleteDuplicate(ListNode *head){
          if(head == nullptr)
              return head;

          for(ListNode *prev = head, *cur = prev->next; cur; cur = cur->next){
                 if(prev->val == cur->val){ 
                      prev->next = cur->next;
                      delete cur;
                  }else{
                      prev = cur;
                  }
             }
           return head;
      }

這里不需要用dummy node, 用一個循環(huán)來遍歷整個linked list,這里注意head其實并沒有改變因此可以直接返回澜薄。

下面增加一定難度为肮，仍然是刪除重復(fù)節(jié)點， 但是只保留沒有重復(fù)的節(jié)點

 ListNode *deleteDuplicate(ListNode *head){
          if(head == nullptr)
             return head;
      
          ListNode dummy(INT_MIN);
          dummy.next = head;
          ListNode *prev = &dummy, *cur = head;
          while(cur){
             bool duplicated = false;
             while(cur->next && cur->next->val == cur->val){
                     duplicated = true;
                     ListNode *tmp = cur;
                     cur = cur->next;
                     delete tmp;
                   }
             if(duplicated){
                  ListNode *tmp = cur;
                  cur = cur->next;
                  delete tmp;
                  continue;
               }
               prev->next = cur;
               prev = prev->next;
               cur = cur->next;
           }
            prev->next = cur;
            return dummy.next;
     }

如果只保留沒有重復(fù)的節(jié)點肤京，復(fù)雜度就提高了颊艳。首先需要一個boolean值來記錄該節(jié)點是否是重復(fù)的，然后需要dummy node因為head也有可能被刪除蟆沫。然后就是雙重循環(huán)在內(nèi)循環(huán)中刪除當(dāng)前節(jié)點籽暇，然后指向下一個節(jié)點。如果是重復(fù)的節(jié)點還需要把最后一個節(jié)點刪除饭庞，然后continue戒悠。整個循環(huán)中prev節(jié)點是不動的，他永遠指向下一個刪除過后的節(jié)點舟山，然后再更新自己绸狐。最后不要忘記鏈接prev和cur兩個節(jié)點。

刪除的一個簡單變化累盗，刪除alternative node采用雙指針iterative方法來處理寒矿，特別注意cur指針更新時候需要判斷prev是否是空指針：

 void deleteAlt(Node *head){
        if(head->next == nullptr) return;

        Node *prev = head, *cur = head->next;
        while(prev && cur){
            prev->next = cur->next;
            delete cur;
            prev = prev->next;
            if(prev)
                cur = prev->next;
       }
   }

Recurive方法是典型的tail-recursive的實例：

  void deleteAlt(Node *head){
        if(head == nullptr) return;
        Node *next = head->next;
        if(next){
             head->next = next->next;
             delete next;
             deleteAlt(head->next);
          }
    }

關(guān)于刪除， Delete N nodes after M nodes of linked list特別注意遍歷鏈表的時候檢查是否走到鏈表的盡頭了若债。

void skipMdeleteN(Node *head, int M, int N){
     Node *cur = head;
     while(cur){
          for(int i = 1; i < M && cur; ++i)
                cur = cur->next;
          if(cur == nullptr) return;
          Node *t = cur->next;
          for(int i = 1; i < N && t; ++i){
                Node *tmp = t;
                t = t->next;
                delete t;
            }
             cur->next = t;
             cur = cur->next;
            }
          }

另一個簡單的例子就是找到linked list第N個節(jié)點,如果沒有找到就返回一個極小值,此時區(qū)別于數(shù)組,這里需要遍歷linked list符相。

 int getNth(Node *head, int N){
    Node *cur = head;
    int count = 0;
    while(cur){
       if(count == n)
         return cur->val;
       count++;
       cur = cur->next;
     }
   return INT_MIN;
 }

利用雙指針的方法，可以用來找到linked list的中間節(jié)點蠢琳，這里不用區(qū)分linked list是偶數(shù)個還是奇數(shù)個node(奇數(shù)和偶數(shù)的唯一區(qū)別在于while循環(huán)的終止條件：奇數(shù)為fast->next ==nullptr啊终；偶數(shù)為fast ==nullptr)：

  void printMid(Node *head){
         Node *slow = head, *fast = head;
         if(head){
              while(fast && fast->next){
                     fast = fast->next->next;
                     slow = slow->next;
                    }
             cout << slow->val << endl;
           }
    }

類似的方法可以用于尋找距離尾部N個位置的節(jié)點：

 Node * findNEnd(Node *head, int n){
          int count  = 0;
          Node *slow = head, *fast = head;
          while(count < n){
                if(fast == nullptr)
                   return nullptr;
                fast = fast->next;
                count++;
          }
         
          while(fast){
              slow = slow->next;
              fast = fast->next;
           }
         
          return slow;
    }

這里需要注意的是在第一個while循環(huán)里面，需要判斷一下fast是否已經(jīng)到達鏈表的尾部傲须，即n的值大于linked list的長度時候需要返回nullptr.

改變結(jié)構(gòu)

類似于array蓝牲，linked list也可以進行rotate,但是相對于array，鏈表需要進行遍歷找到改變的節(jié)點位置泰讽。Rotate a linked list

Node *rotate(Node *head, int k){
      if(head == nullptr) return head;
      Node *cur = head, *new, *last;
      for(int i = 1; i < k && cur; ++i)
              cur = cur->next;

      new = cur->next; last = new;
      cur->next = nullptr;
      while(last->next)
             last = last->next;
      last->next = head;

      return new;
  }

這里有個地方要注意例衍，需要檢查k是否超過了linked list的總長度昔期，也就是在循環(huán)中加一個條件cur != nullptr.
對于linked list有很多問題圍繞在改變原來linked list的node之間的順序，比如下面這道題：將原來的linked list中在偶數(shù)位置的節(jié)點按照倒序方式接在linked list的末尾佛玄。

 void modify(Node *head){
      if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
          return;

      Node *first = head, *second = first->next;
      first->next = first->next->next;
      first = first->next;
      second->next = nullptr;

      while(first && first->next){
            Node *tmp = first->next;
            first->next = first->next->next;
            tmp->next = second;
            second = tmp;
            first = first->next;
      }
      first->next = second; 
}

這里需要注意幾個問題硼一，首先如果linked list不超過三個節(jié)點那么沒有任何節(jié)點的順序需要改變，然后就是需要雙指針一個用來記錄當(dāng)前奇數(shù)位的節(jié)點另一個用來記錄偶數(shù)位的節(jié)點梦抢，注意偶數(shù)位的節(jié)點需要用倒序的方式添加新的節(jié)點欠动，整個過程像構(gòu)建了兩個linked list最后在頭尾相連完成整個函數(shù)的構(gòu)建。如果是對于原來的linked list倆倆互換的情況呢惑申？
Swap Nodes in Pairs
第一種偷懶的方法就是直接互換節(jié)點的數(shù)值：

Node *pairswap(Node *head){
         Node *p = head;

         while(p && p->next){
              swap(p-val, p->next->val);
              p = p->next->next;
             }
      }

下面看如何倆倆互換節(jié)點的指針來解決問題,首先討論特殊情形具伍，即一共有少于兩個節(jié)點，那么只要返回原linked list就可以了圈驼。接著創(chuàng)建一個dummy node,接著需要三個node, prev, cur, next人芽，每次需要互換cur和next,之后在update三個節(jié)點。在更新next節(jié)點時候需要判斷cur是否存在绩脆，如果不存在則設(shè)為nullptr,因此整個循環(huán)的判斷也是next是否為nullptr萤厅。

  Node *pairswap(Node *head){
           if(head == nullptr || head->next == nullptr) return head;
           Node dummy(-1);
           dummy.next = head;
           for(Node *prev = &dummy, *cur = prev->next, *next = cur->next; next; prev = cur,  
                 cur=cur->next, next = cur? cur->next: nullptr){
                 prev->next = next;
                 cur->next = next->next;
                 next->next = cur;
            }
          return dummy.next;
   }

在上面的問題基礎(chǔ)上，我們看一下如何對一個linked list反轉(zhuǎn)靴迫，對于array反轉(zhuǎn)是很容易的惕味，因為array可以直接對每一對頭尾的元素倆倆交換從兩頭向中間靠攏，array查找是常數(shù)時間復(fù)雜度玉锌。但是對于singly linked list只有單向的遍歷因此如果需要向前遍歷則需要從頭開始遍歷名挥。鑒于以上情形，linked list的反轉(zhuǎn)需要三個節(jié)點, prev指向的最前面的那個節(jié)點主守， cur指向當(dāng)前節(jié)點或者中間的節(jié)點禀倔，next指向的是下一個節(jié)點。首先我們先看一下迭代的方法参淫，總體來說就是在循環(huán)里面讓cur->next指向prev, 這樣prev用cur來代替救湖，然后cur用next來替換。整個循環(huán)的作用就是把prev node和current node之間的前后關(guān)系顛倒過來涎才，并且current node和next node之間的連接關(guān)系斷開鞋既。注意這里不可以使用dummy node的技術(shù)，因為reverse之后dummy node會變?yōu)樽詈笠粋€node這樣比原來的linked list要多出一個節(jié)點耍铜。

     Node* reverse(Node * head){
          Node *prev = nullptr, *cur = head, *next;
          while(cur){
               next = cur->next;
               cur->next = prev;
               prev = cur;
               cur = next;       
            }
        return prev;
      } 

在看一下遞歸方法：

 void reverse(Node **head){
     Node *first, *rest;
     if(*head == nullptr || (*head)->next == nullptr)
         return;

     first = *head;
     rest = first->next;
        
     recursive(&rest);
     first->next->next = first;
     first->next = nullptr;

     *head = first;
   }

遞歸方法中把linked list分為兩段邑闺，head和其他部分，其他部分作為新的head傳入到recursive function里面业扒，之后在顛倒head及其后面節(jié)點的順序检吆，最后再update head node舒萎。 在以上的基礎(chǔ)上程储，還可以進一步的簡化遞歸過程如下：

  Node *reverse(Node *cur, Node *prev){
         if(cur == nullptr) return prev;
         Node *last = reverse(cur->next, cur);
          cur->next =prev;
          return last;
      }

接著通過擴展前面?zhèn)z倆交換的例子現(xiàn)在變?yōu)橐詋個node為一個單位reverse linked list.

 Node *reverseKGroup(Node *head, int k){
        if(head == nullptr|| head->next == nullptr || k < 2) return head;
         Node dummy(-1);
         dummy.next = head;
         for(Node * prev = &dummy, end = head; end; end = prev->next){
                for(int i = 1; i < k && end; ++i)
                         end = end->next;

                 if(end == nullptr)
                       break;

                 prev = reverse(prev, prev->next, end);
            }
        return dummy.next;
     }

Node *reverse(Node *prev, Node *begin, Node *end){
       Node *end_next = end->next;
       for(Node *p = prev, *cur = prev->next, *next = cur->next; cur != end_next;
             p = cur, cur = next, next = next?next->next:nullptr){
             cur->next = p;
          }
      begin->next = end->next;
      prev->next = end;
      return begin;
 }

這里有幾個需要注意的地方： 如果k<2或者linked list的節(jié)點數(shù)不超過兩個蹭沛， 原linked list保持不變；在循環(huán)中始終需要查看end節(jié)點是否存在章鲤，如果end為空表明指針走到了linked list的尾端整個循環(huán)應(yīng)該停止摊灭；這里的reverse函數(shù)與之前的reverse linked list本質(zhì)是一樣的，只是在循環(huán)中加了關(guān)于結(jié)尾指針的判斷cur != end_next（之前只需要判斷cur != nullptr败徊，因為cur在整個linked list的最后一個節(jié)點必然是nullptr). 下面把問題稍微增加一點復(fù)雜度: Reverse alternative K nodes in a Singly linked list.

  Node *kAltReverse(Node *head, int k){
            if(head == nullptr || head->next == nullptr || k < 2) return head;
            Node dummy(-1);
            dummy.next = head;
            for(Node *prev = &dummy, *end = head, int i = 0; end; end = prev->next){
                        for(int j = 1; j < k && end ; ++j){
                                   end = end->next;
                                   ++i;
                             }
                      
                        if(end == nullptr) break;
                        
                        if(i %(2*k) > 0)
                             prev = reverse(prev, prev->next, end);
                        else
                             prev = end;
                  }
          
            return dummy.next;
        }

   Node *reverse(Node *prev, Node *begin, Node *end){
           Node *end_next = end->next;
           for(Node *p = prev, *cur = prev->next, *next = cur->next; cur != end_next;
                p = cur, cur = p->next; next= next? next->next; nullptr){
                    cur->next = p;
                 }
               
                begin->next = end_next;
                prev->next = end;
                return begin;
         }

這道題增加了一個判斷條件i%(2k)*來判斷是否需要reverse,另外需要注意的是當(dāng)不需要reverse時候prev指針的更新帚呼。接著看這道題: 給定一個linked list對于偶數(shù)位的node reverse并且接在奇數(shù)位的node之后。

  void modify(Node *head){
            if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
                 return;
      
            Node *first = head, *second = head->next;
            first->next = first->next->next;
            first  = first->next;
            second ->next = nullptr;

            while(first && first-next){
                Node *tmp = first->next;
                first->next = first->next->next;
                tmp->next = second;
                second = tmp;
              }
          first->next = second;
     }

這里用兩個pointer分別記錄偶數(shù)位的node和奇數(shù)位的node,對于偶數(shù)位的reverse沒有按照之前的方法用三個指針來做皱蹦，而是把遍歷到新的偶數(shù)位node添加在目前的偶數(shù)pointer(second)的前面,這樣可以做到reverse on the fly一次遍歷就可以把整個問題解決煤杀。接下來看一個綜合以上的幾個題目的題目，判斷l(xiāng)inked list是否是palindrome.最直觀的方法就是用一個stack沪哺，然后遍歷整個linked list,push every node到stack里面沈自，然后做第二遍遍歷時候pop stack然后與當(dāng)前l(fā)inked list里面的node進行比較，如果遍歷下來所有node都一致那么就是palindrome反之就不是辜妓。下面再看一個解法：

 bool isPalindrome(Node *head){
        Node *slow = head, *fast = head;
        Node *second , *prev_slow = head;
        Node *mid_node = nullptr;
   
        bool res = true;
        if(head == nullptr || head->next == nullptr) return res;
        
        while(fast && fast->next){
             prev_slow = slow;
             slow = slow->next;
             fast = fast->next->next;
           }

         if(fast){
               mid_node = slow;
               slow = slow->next;
          }

         second = slow;
         prev_slow ->next = nullptr;
         reverse(&second);
         res = compare(head, second);
       
         reverse(&second);
         if(mid_node){
              prev_slow->next = mid_node;
              mid_node->next = second;
          }
             prev_slow->next = second;
         return res;
      }

   void reverse(Node **head){
         Node *prev = nullptr, *cur = *head, *next;
         while(cur){
             next = cur->next;
             cur->next = prev;
             prev = cur;
             cur= next;
         }
        *head = prev;
    }

  bool compare(Node *first, Node *second){
         Node *p1 = first, *p2 = second;
         while(p1 && p2){
              if(p1->val == p2->val){
                    p1 = p1->next;
                    p2 = p2->next;
               }else
                     return false;
           }
            
           if(p1 == nullptr && p2 == nullptr)
                return true;
   
        return false;
    }

這個解法結(jié)合了上面的linked list reverse和雙指針方法尋找mid point枯途，但是由于在reverse linked list過程中破壞了原來linked list的結(jié)構(gòu)，因此需要再一次reverse進行復(fù)原籍滴，在時間消耗上是比較費事的酪夷。另外在compare這個函數(shù)中，最后采用判斷p1和p2是否同時為空比較巧妙孽惰， compare函數(shù)本身可以作為一個經(jīng)典的兩個linked list比較問題晚岭。 為了避免改變linked list的原來結(jié)構(gòu)，可以采用雙指針遞歸的方法：

bool isPalindromUnit(Node *&left, Node *right){
         if(right == nullptr)
              return true;

         bool isp = isPalindromUnit(left, right->next);
         if(!isp) return false;

         bool ispl = (right->val == left->val);
         left = left->next;

         return ispl;
  }

 bool isPalindrom(Node *head){
        isPalindrom(head, head);
 }

這個解法有幾個注意的地方勋功，第一個就是base case的討論腥例，如果right pointer已經(jīng)到達linked list的尾部（==nullptr）那么返回true,另外left pointer需要pass by reference這里用的是*&也可以用pointer to pointer來表示。最后一點這里不是tail-recursive call酝润，算上遞歸椓鞘空間是O(n).
Linked List問題有時候可以增加一些復(fù)雜性，但是本質(zhì)上還是與傳統(tǒng)的問題是一致的要销，比如說這道題Given a linked list of line segments, remove middle points, 具體的要求可以查看鏈接构回，這道題的核心是需要三個節(jié)點來判斷中間節(jié)點是否需要刪除。

 Node *removeMid(Node *head){
           Node *cur = head;
           while(cur && cur->next && cur->next->next){
                   Node *mid = cur->next;
                   Node *last = mid->next;
                   if(mid->x == last->x && cur->x == mid->x || cur->y == mid->y && mid->y == last->y){
                    cur->next = last;
                    delete mid;
                }else if(cur->x == mid->x && mid->x != last->x||(cur->y == mid->y && mid->y != last->y){
                    cur->last;
                }else{
                    cout << "Invalid" << endl;
                    eixt(1);
                }        
             }
          return head;
       }

接下來看一道題對于結(jié)構(gòu)變化的linked list,怎樣判斷一個linked list是否有l(wèi)oop?

   bool hasCycle(ListNode *head){
           ListNode *slow = head, *fast = head;
           while(fast && fast->next){
                 fast = fast->next->next;
                 slow = slow->next;
                 if(slow == fast)
                     return true;
             }
          return false;
     }

Follow up, 如果需要返回cycle開始的節(jié)點呢?

 ListNode * detectCycle(ListNode *head){
            ListNode *slow = head, *fast = head;
            while(fast && fast->next){
                  fast = fast->next->next;
                  slow = slow->next;
                  if(slow == fast){
                      slow = head;
                      while(slow != fast){
                          slow = slow->next;
                          fast = fast->next;
                      }
                      return slow;
                  }
              return nullptr;
       }

還有一道綜合題疏咐，結(jié)合了reverse linked list和節(jié)點刪除的技巧
delete nodes which have a greater value on right side:當(dāng)然永遠可以使用暴力的解法采用雙重循環(huán)檢查每一個節(jié)點看是否有右邊的節(jié)點擁有更大的數(shù)值纤掸，但是復(fù)雜度將達到O(n^2),下面的解法可以達到線性計算時間。

 void delLesserNodes(Node **head_ref){
          reverseList(head_ref);
          _delLesserNode(*head_ref);
          reverseList(head_ref);
  }

  void reverseList(Node **head){
      Node *cur = head, *prev, *next;
       while(cur){
           next = cur->next;
           cur->next = prev;
           prev = cur;
           cur = next;
        }
        *head = prev;
     }

   void _delLesserNode(Node *head){
          Node *current = head, maxNode = head;
          Node *tmp;
          while(current && current->next){
               if(current->next->val < maxNode->val){
                      tmp = current->next;
                      current->next = tmp->next;
                      delete tmp;
                 }else{
                     current = current->next; 
                     maxnode = current; 
                 }
              }
       }

首先需要reverse linked list浑塞，然后一個個比較最大節(jié)點與當(dāng)前節(jié)點的數(shù)值借跪，如果當(dāng)前節(jié)點的數(shù)值小則刪除當(dāng)前節(jié)點，最后還原linked list的結(jié)構(gòu)酌壕。
當(dāng)linked list中的value是特殊的數(shù)值時掏愁，排序linked list也可以采用特殊的方法歇由。比如linked list只含有0, 1 ,2數(shù)值，排序linked list.

void sortList(Node *head){
        vector<int> tmp(3,0);
        Node *cur = head;
        while(cur){
           if(cur->val == 0){
                 tmp[0]++;
             }else if(cur->val == 1){
                 tmp[1]++;
             }else{
                 tmp[2]++;
             }
              cur = cur->next;
          }

          cur = head;
          while(cur){
              if(tmp[i] == 0)
                ++i;
              else{
                cur->data = i;
                --tmp[i];
                cur = cur->next;
               }
             }
         }

這里采用vector相當(dāng)于一個hash table記錄0,1, 2的個數(shù)果港，code還可以寫的更簡潔一些：

  void sortList(Node *head){
        vector<int> count(3, 0);
        Node *ptr = head;
        while(ptr){
             count[ptr->val]++;
             ptr = ptr->next;
         }
         int i = 0;
         ptr = head;

         while(ptr){
            if(count[i] == 0)
               ++i;
            else{
               ptr->val = i;
               --count[i];
               ptr = ptr->next;
              }
            }
          }

兩個或者多個linked list的問題

首先看一下如何將一個linked list分成兩個：

 void AltSplit(ListNode *source, ListNode **a, ListNode **b){
          ListNode dummyA(-1);
          ListNode dummyB(-1);
          ListNode *cur = source, *ta = &dummyA, *tb = &dummyB;
          while(cur && cur->next){
              ta->next = cur;
              tb->next = cur->next;
              ta = ta->next;
              tb = tb->next;
           }
          if(cur) ta->next = cur;
          *a = dummyA.next;
          *b = dummyB.next;
    }

Merge 兩個 sorted linked list, 由于linked list本身已經(jīng)排好序沦泌，可以通過比較兩個list node的值大小來merge,若節(jié)點為空則設(shè)置為無窮大。

   ListNode *mergeList(ListNode *a, ListNode*b){
                 ListNode dummy(-1);
                 for(ListNode *cur = &dummy; a||b; cur=cur->next){
                      int valA = (a == nullptr)? INT_MAX: a->val;
                      int valB = (b == nullptr)? INT_MAX: b->val;
                      if(valA < valB){
                         cur->next = a;
                         a = a->next;
                      }else{
                         cur->next = b;
                         b = b->next;
                      }
                }
           return dummy.next;
   }

當(dāng)然也可以通過一個個確認節(jié)點是否為空來merge:

    ListNode *mergeList(ListNode *a, ListNode *b){
              if(a == nullptr) return b;
              if(b == nullptr) return a;
              ListNode dummy(-1);
              ListNode * result = &dummy;
              for( ; a && b; result = result->next){
                   if( a->val < b->val){
                         result->next = a;
                         a = a->next;
                     }else{
                         result->next = b;
                         b = b->next;
                     }
                 }
               result->next = (a? a : b);
           return dummy.next;
      }

對于兩個list辛掠，經(jīng)典題型有尋找兩個linked list的intersection

  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(headA == nullptr || headB == nullptr) return nullptr;
    ListNode *curA = headA, *curB = headB;
    ListNode *tailA = nullptr, *tailB = nullptr;

    while(true){
       if(curA == nullptr)
          curA = headB;
        
       if(curB == nullptr)
          curB = headA;
           
       if(curA->next == nullptr)
           tailA = curA;
    
       if(curB->next == nullptr)
           tailB = curB;
           
       if(tailA && tailB && tailA->val!= tailB->val) return nullptr;
       
       if(curA == curB) return curA;
       
       curA = curA->next;
       curB = curB->next;
    }

這道題的關(guān)鍵linked list A的尾部鏈接到linked list B的頭部谢谦，同樣linked list B的尾部鏈接到linked list A的頭部。提前可以判斷的是如果兩個linked list的尾部不等那么肯定沒有intersection,只有當(dāng)一個時刻兩個pointer指向同一個節(jié)點那么它就是intersection.

如果linked list本身是有序的萝衩，尋找intersection假設(shè)這樣的intersection是存在的：

 Node *intersect(Node *a, Node *b){
     Node dummy(-1);
     Node *cur = &dummy;
     while(a && b){
        if(a->val == b->val){
           cur->next = a;
           cur = cur->next;
           a = a->next;
           b = b->next;
        }else if(a->val < b->val){
                 a = a->next;
        }else{
              b = b->next;
         }
         cur->next = nullptr;
         return dummy.next;
   }

這里采用了dummy node的方法回挽，類似于之前的merge方法，只是選擇數(shù)值相同的節(jié)點猩谊。另外需要注意的是兩個linked list的節(jié)點更新厅各。下面是遞歸的方法：

 Node *intersect(Node *a, Node *b){
        if(a == nullptr || b == nullptr)
              return nullptr;

        if(a->data < b->data)
               return intersect(a->next, b);

        if(a->data > b->data)
                return intersect(a, b->next);

        Node *tmp = new Node(a->data);
        tmp->next = Intersect(a->next, b->next);
        return tmp;
   }

同樣是two sorted linked list, construct a maximum sum linked list out of them:

 void findMaxSumlist(Node *a, Node *b){
         Node *result =  nullptr;
         Node *pre1 = a, *cur1 = a; 
         Node *pre2 = b, *cur2 = b;

         while(cur1 || cur2){
             int sum1 = 0, sum2 = 0;
             while(cur1 && cur2 && cur1->data != cur2->data){
                   if(cur1->data < cur2->data){
                        sum1+= cur1->data;
                        cur1 = cur1->next;
                     }else{
                        sum2 += cur2->data;
                        cur2 = cur->next;
                     }
            }

            if(cur1 == nullptr){
                 while(cur2){
                    sum2 += cur->data;
                    cur2 = cur2->next;
                   }
               }

           if(cur2 == nullptr){
                while(cur1){
                    sum1 += cur->data;
                    cur1 = cur1->next;
                  }
             }
    
           if(pre1 == a && pre2 ==b)
                  result = (sum1 > sum2)? pre1 : pre2;
           else{
                  if(sum1 > sum2)
                      pre2->next = pre1->next;
                  else
                      pre1->next = pre2->next;
              }

                pre1 = cur1, pre2 = cur2;

             if(cur1)
                  cur1 = cur1->next;

            if(cur2)
                  cur2 = cur2->next;
         }
          while(result){
               cout << result->data << " ";
               result = result->next;
           }
        }

這道題的思路是在使用merge的同時，一直記錄到達到共同的節(jié)點之前各自鏈表所有節(jié)點之和预柒，比較兩者之后選擇是否更新prev節(jié)點使得最后的結(jié)果得到最大的和队塘。
當(dāng)linked list代表一個數(shù)字時候，兩個數(shù)的加法可以用linked list操作來進行宜鸯。

 Node *addTwoList(Node *first, Node *second){
    Node *result, *temp, *prev;
    int carry = 0, sum;

    while(first || second){ 
         sum = carry + (first? first->data: 0) + (second? second->data: 0);
     
         carry = sum/10;
         sum = sum%10;
          
        temp = new Node(sum);
        
        if(result == nullptr)
              result = temp;
        else
              prev->next = temp;
     
        prev = temp;

        if(first) first = first->next;
        if(second) second = second->next;
       }
  
    if(curry) 
       temp->next = new Node(carry);

    return result;
} 

如果linked list結(jié)構(gòu)發(fā)生一些變化憔古，比如說node本身不僅指向下一個Node，還有一個額外的random Node,如何clone

  RandomListNode *copyRandomList(RandomListNode *head){
           for(RandomListNode *cur = head; cur; ){
                RandomListNode *newNode = new RandomListNode(cur->label);
                newNode->next = cur->next;
                cur->next = newNode;
                cur = cur->next->next;
             }
            
           for(RandomListNode *cur = head;cur; ){
              if(cur->random){
                 cur->next->random = cur->random->next;

              cur = cur->next->next;
            }

           RandomListNode dummy(-1);
           dummy.next = head;

          for(RandomListNode *prev = &dummy, *cur = head;cur;){
                  prev->next = cur->next;
                  prev = prev->next;
                  cur->next = cur->next->next;
                  cur = cur->next;
            }

          return dummy.next;
       }

這道題的傳統(tǒng)做法需要復(fù)制原來鏈表所有的節(jié)點和random節(jié)點淋袖，對于空間的要求是O(n)鸿市，或者用hashtable記錄所有的label來記錄random節(jié)點和next節(jié)點位置。這里巧妙第一次遍歷在原linked list中每一個節(jié)點后復(fù)制其自身即碗，然后第二次遍歷將cur節(jié)點random pointer信息復(fù)制出去通過cur->next焰情。最后就是將一個linked list分開成兩個linked list.

類似于在array里面的3sum問題，分別從三個linked list里面找到一個節(jié)點使得之和為一個給定數(shù)剥懒。通過之前3sum的問題我們可以發(fā)現(xiàn)array需要排序來縮小搜索范圍内舟，所以我們對其中一個linked list b生序排序，另一個linked list c降序排序初橘，然后再進行類似3sum的操作验游，以下程序假設(shè)排序已經(jīng)完成以后的操作：

  bool isSumSorted(Node *aHead, Node *bHead, Node *cHead, int x){
          Node *a = aHead;
          while(a){
               Node *b = bHead;
               Node *c = cHead;
               while(b && c){
                   int sum = a->val  + b->val + c->val;
                   if(sum == x){
                       cout << a->val << " " << b->val << " " << c->val << endl;
                       return true;
                    }else if( sum < x){
                       b = b->next;
                    }else{
                       c = c->next;
                    }
                a = a->next;
              }
         return false;
      }