1.反轉單鏈表

題目

方法一：原地改變原鏈表的指向

這種方法很容易理解，實作也比較方便，只需要用三個指標，分別為前一個位置，當前位置，后一個位置來完成就可以實作

代碼實作

struct ListNode* reverseList(struct ListNode* head)
{
    // 改變原鏈表的指向
    struct ListNode* cur=head;
    if(head==NULL)
    {
        return head;
    }
    struct ListNode* nnext=head->next;
    struct ListNode* pre=NULL;
    while(cur)
    {
        cur->next=pre;
        pre=cur;
        cur=nnext;
        if(nnext!=NULL)
        {
            nnext=nnext->next;
        }
    }
    head=pre;
    return head;
}

方法二：頭插法

圖解頭插法

代碼實作

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //頭插新節點，更新頭
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    
    return newhead;
}

方法三：遞回

代碼實作

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

2. 鏈表中間節點

題目

方法一：記錄總共多少個節點，然后找到它的一半的那個節點

實作代碼

struct ListNode* middleNode(struct ListNode* head)
{
//方法一：記錄總共多少個節點，然后找到它的一半的那個節點
     int n=0;
     struct ListNode* tail=head;
     if(tail!=NULL)
     {
         n=0;
     }
     else
     {
         return NULL;
     }
     while(tail)
     {
         n++;
         tail=tail->next;
     }
     int middlenum=(n/2)+1;
     struct ListNode* middle=head;
     while(--middlenum)
     {
         middle=middle->next;
     }
     return middle;
 }

方法二：快慢指標

方法一這種方法容易想出，也不算太復雜，那有沒有更快的方法了？ 下面我們迎來了一種全新的方法快慢指標，在這道題目里面，我們讓快指標一次走兩步，慢指標一次走一步，當快指標走到尾節點時，慢指標此時恰好在中間節點，這個道理也很容易想明白，因為快指標走的速度是慢指標的兩倍，所以當快指標到尾時，慢指標才會在中間，快慢指標這種全新的方法在很多其他題目里面也非常的好用

代碼實作

  struct ListNode* slow=head;
      struct ListNode* quick=head;
      while(quick!=NULL&&quick->next!=NULL)
      {
          slow=slow->next;
          quick=quick->next->next;
      }
      return slow

3.鏈表中倒數第k個結點

題目

方法一：記錄總共多少，然后輸出倒數k個（懸疑問題）

這種方法也是受前一題中間節點的那種計數的方法影響，看看這邊是否也可以，但寫了一下發現總是過不了，代碼感覺也沒有問題，希望懂得小伙伴可以幫忙看看

代碼實作

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    int n=0;
    struct ListNode* tail=pListHead;
    struct ListNode* ans=pListHead;
    while(tail)
    {
        n++;
        tail=tail->next;
    }
    if(k>n&&k<=0)
    {
          return NULL;
    }
    else
    {
     int find=n-k+1;
    while(--find)
    {
        ans=ans->next;
    }
    return ans;
    }
}

方法二，快慢指標

我們可以讓快的指標先走k步，以此來達到此目的，所以說快慢指標在有些題中用過是很大的

代碼實作

    struct ListNode*slow=pListHead;
    struct ListNode* fast=pListHead;
    while(k--)
    {
        if(fast)
        {
            fast=fast->next;
        }
        else
        {
            return NULL;
        }
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;

4.合并兩個有序鏈表

題目

解題方法

在看完題目之后，我對這題大概就知道解法了，可以創建一個新的鏈表，然后以此挑選小的來當來，這里面要注意如果移動，以及一些邊界情況

代碼實作

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
      struct ListNode*newhead=NULL;
      struct ListNode* p1=l1;
      struct ListNode* p2=l2;
      struct ListNode*tail=NULL;
      if(p1==NULL&&p2==NULL)
      {
          return NULL;
      }
      else if(p1!=NULL&&p2==NULL)
      {
          return p1;
      }
      else if(p2!=NULL&&p1==NULL)
      {
          return p2;
      }
      if(p1->val<p2->val)
      {
          newhead=p1;
          p1=p1->next;
      }
      else
      {
          newhead=p2;
          p2=p2->next;
      }
      tail=newhead;
      while(p1&&p2)
      {
          if(p1->val<p2->val)
          {
              tail->next=p1;
              tail=p1;
              p1=p1->next;
          }
          else
          {
              tail->next=p2;
              tail=p2;
              p2=p2->next;
          }
      }
      if(p1==NULL)
      {
          tail->next=p2;
      }
      if(p2==NULL)
      {
          tail->next=p1;
      }
      return newhead;
}

5.鏈表分割

題目

解決方法

在看完題目后，我第一反應是建立一個新的鏈表，然后將小于x的尾插進去，然后想著想著，發現單單建立一個是不行的，要兩個鏈表才可以，一個存放小于x的，一個存放大于x等于x的，但我在這小的程序中犯了一個很重要的錯誤，就是鏈表節點之間的指向，如果你分下來分，換句話說，你沒有在一個while回圈里面把大于等于x和小于x的元素分開，這樣會導致元素之間的指向關系混亂，下面大家也可以看看這段代碼，以此為戒，

Bug代碼

        struct ListNode* newhead=NULL;
        struct ListNode* tail=NULL;
        struct ListNode* cur=pHead;
        struct ListNode* bighead = NULL;
	    struct ListNode* bigtail = NULL;
        while(cur)
        {
            if(cur->val<x)
            {
                newhead=cur;
                tail=newhead;
                break;
            }
            else
            {
                cur=cur->next;
            }
        }
        if(cur==NULL)
        {
            return pHead;
        }
        else
        {
            cur=cur->next;
            while(cur)
            {
                if(cur->val<x)
                {
                    tail->next=cur;
                    tail=cur;
                    cur=cur->next;
                }
                else
                {
                    cur=cur->next;
                }
            }
        }
        tail->next=NULL;
        cur=pHead;
        while(cur)
        {
            if(cur->val>x||cur->val==x)
            {
                bighead=cur;
                bigtail=bighead;
                break;
            }
            else
            {
                cur=cur->next;
            }
        }
        if(cur==NULL)
        {
            return pHead;
        }
        else
        {
               cur=cur->next;
                  while(cur)
              {
                   if(cur->val>x||cur->val==x)
                  {
                     bigtail->next=cur;
                     bigtail=cur;
                     cur=cur->next;
                  }
                  else
                  {
                     cur=cur->next;
                  }
              }
        }
    bigtail->next = NULL;
	tail->next = bighead;
    return newhead;

正確解決

        if(pHead == NULL)
            return NULL;
        
        struct ListNode* lessHead, *lessTail,*greaterHead, *greaterTail;
        //創建鏈表表頭
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while(cur)
        {
            //小于x的尾插到lessTail
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            //大于等于x的尾插到greaterTail
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        //鏈接兩個鏈表
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        //獲取表頭
        pHead = lessHead->next;
        free(lessHead);
        free(greaterHead);
        
        return pHead;

其實當我實在是修改不了那段bug代碼后，看正確代碼的時候，發現還是應該在寫代碼前把思路理順，想想怎么寫才是最優化的，是什么問題導致我這個bug的，我可不可以避開這個問題了？如果我在寫的時候或者寫之前把這些想明白，可能也就不會寫出那段bug代碼，