链表的经典入门LeetCode题目

常用函数 

//链表翻转
struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

//询查链表中点
struct ListNode* get_mid(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast->next&& fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

19. 删除链表的倒数第 N 个结点d

第一种方法：

//函数目的:求链表的长度  参数(头指针)
int getLength(struct ListNode* head)
{
    int length=0;
    while(head){
        ++length;
        head=head->next;
    }
    return length;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* dummy_node = malloc(sizeof(struct ListNode));//创建哑结点
    dummy_node->val=0,dummy_node->next=head;//dummy_node 指向 head 赋值

    int length = getLength(head);  //获取长度

    struct ListNode* cur = dummy_node; //创建一个结点用于操作链表
    for(int i=1;i<length-n+1;i++)
    {
        cur = cur->next;//最后目的为让 cur-> length-n+1的前一个结点
    }
    cur->next = cur->next->next;//指向 length -n+1 的后一个结点

    struct ListNode* ans = dummy_node->next;
    free(dummy_node);//malloc操作后要释放  如果不释放 直接return dunmmy_node->next;就好了 也不需要上面一句话
    return ans;
}

第二种快慢指针

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val=0;dummy->next=head;
    struct ListNode* first;
    struct ListNode* second;
    first = head, second = dummy;
    for(int i=1;i<=n;i++)//n==2  1 < 2  2 <= 2
        first = first->next;
    while(first)
    {
        first = first->next;
        second = second->next;
    }
    second->next=second->next->next;
    struct ListNode* ans ;
    ans = dummy->next;
    free(dummy);
    return ans;
}

206. 反转链表

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL;
    struct ListNode* cur  = head;
    while(cur!=NULL)
    {
        struct ListNode* Next = cur->next;
        cur->next=prev;
        prev = cur;
        cur = Next;
    }
    return prev;
}


/*
 *  要让 1 -> 2 -> 3 -> Null  变成 3 -> 2 -> 1 -> Null
 *  第一步是 设置三个结点  一个当前结点 cur 一个为先前结点 prev 一个为后继结点 next
 *  先要 1->2 断开链接 让1->null 
 *  再让 prev 变为 cur   cur 变为 next 重复到 cur 变为 NULL
 */

92. 反转链表 II

思路：

让前继结点pre到m所在位置的前一个位子，再让cur指向left所在的位子，交换顺序是cur指向后继结点Next指向的结点，Next指向cur,pre指向Next。(最好自己画图对着代码理解！！)

struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
  struct ListNode* dummy = malloc(sizeof(struct ListNode));
  dummy->val=0,dummy->next=head;
  struct ListNode* pre = dummy;
  for(int i=1;i<left;i++)// 1<2
     pre = pre->next;
  struct ListNode* cur = pre->next;
  for(int i=0;i<right-left;i++) //0<2 1<2
  {
      struct ListNode* Next = cur->next;
      cur->next = Next->next;
      Next->next = pre->next;
      pre->next=Next;
  }
  return dummy->next;
}

141. 环形链表

思路：快慢指针 环形链表快慢指针会相等 且 不会指向NULL

bool hasCycle(struct ListNode *head) {
    struct ListNode * slow = head,* fast = head;
    while(fast && fast->next )  //fast不为NULL 与 fast.next不为NULL  单链表最后结点指向NULL
    {
        slow = slow->next;
        fast = fast->next->next;   
        if(fast == slow)
            return true;
    }
    return false;
}

142. 环形链表 II

slow = x + y  fast = x + y + n(y+z)  

 2 * slow = fast 

x =  n(y+z) - y  = (n-1)(y+z) + z

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

876. 链表的中间结点

 如果结点个数为偶数

要让中间点落在右边  条件是 while(fast.next && fast.next.next)  （一定要先fast.next 在左边）
要让中间点落在左边 条件是 while(fast && fast.next)

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head,* slow = head;
    while(fast->next&&fast->next->next)
    {
        fast  = fast->next->next;
        slow  = slow->next;
    }
    return slow;
}

143. 重排链表

思路：1.快慢指针找到中点 2.拆成两个链表 3.遍历两个链表，后面的塞到前面的“缝隙里”

涉及一些基本操作

struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* Next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = Next;
    }
    return pre;
}

struct ListNode* get_mid(struct ListNode* head)
{
    struct ListNode* slow = head,* fast  =head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

void merge(struct ListNode* l1,struct ListNode* l2)
{
    while(l1 && l2)
    {
        struct ListNode* n1 = l1->next,* n2 =l2->next;
        l1->next=l2;
        l2->next=n1;
        l1=n1,l2=n2;
    }

}


void reorderList(struct ListNode* head){
     struct ListNode* mid =get_mid(head);
     struct ListNode* nxt = reverse(mid->next);
     mid->next=NULL;
    merge(head,nxt);
}

21. 合并两个有序链表

思路：新建一个链表用于存放数组，结尾再返回。主要是通过比较两个链表的大小。

执行用时：0 ms,   在所有 C 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C 提交中击败了30.36%的用户

truct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* dummy= malloc(sizeof(struct ListNode)) ,* cur =dummy;
    dummy->val =0,dummy->next=NULL;
      while(list1 && list2){
          if(list1->val<=list2->val){
              cur->next = malloc(sizeof(struct ListNode));
              cur->next->val=list1->val;
              list1 = list1->next;
          }
          else{
              cur->next = malloc(sizeof(struct ListNode));
              cur->next->val=list2->val;
              list2 = list2->next;
          }
          cur = cur->next;
      }
      cur->next = list1!=NULL ? list1 : list2;
    return dummy->next;
}

160. 相交链表

方法一：获取链表的长度进行比较，让长的链表移动多出的距离。后面再进行比较。

int get_length(struct ListNode *head)
{
    int length =0;
    while(head){
        length++;
        head=head->next;
    }
    return length;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   int length_a = get_length(headA),length_b = get_length(headB);
   int diff=0;
   struct ListNode * p_a = headA, * p_b =headB;
   if(length_a>=length_b)
   {
       diff = length_a - length_b;
       while(diff)
       p_a = p_a->next;
   }
   else
   {
       diff= length_b-length_a;
       while(diff)
       p_b = p_b->next;
   }
   while(p_a!=p_b)
   {
       p_a=p_a->next;
       p_b=p_b->next;
       if(p_a ==p_b)
           return  p_a;
   }
   return NULL;
}

203. 移除链表元素s

思路：代码一看就懂

//执行用时：8 ms, 在所有 C 提交中击败了97.19%的用户
//内存消耗：8 MB, 在所有 C 提交中击败了40.57%的用户

struct ListNode* removeElements(struct ListNode* head, int val){
     struct ListNode* dummy = malloc(sizeof(struct ListNode));
     dummy->next=head,dummy->val=0;
     struct ListNode* prev = dummy;
      while(prev->next){
          if(prev->next->val==val){
              prev->next=prev->next->next;
          }
          else
              prev=prev->next;
      }
    return dummy->next;
}

82. 删除排序链表中的重复元素 II

struct ListNode* deleteDuplicates(struct ListNode* head){
   struct ListNode* dummy = malloc(sizeof(struct ListNode));
   dummy->next=head,dummy->val=0;
   struct ListNode* p  =dummy;
   while(p->next){
      struct ListNode* q = p->next;
       while (q->next && q->next->val == q->val)   q =q->next;
       if(q ==p->next) 
           p = p->next;
       else
           p->next = q->next;
   }
    return dummy->next;
   }