Leetcode常見鏈表問題及代碼示例

更新時間：2020年11月30日 10:40:30 作者：codeg

這篇文章主要介紹了Leetcode常見鏈表問題及代碼示例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

按規(guī)定區(qū)間反轉(zhuǎn)鏈表

思路：可以考慮成一種把前后數(shù)字的結(jié)點斷開重新組合的問題

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode *dummy = new ListNode(-1), *pre = dummy;
    dummy->next = head;
    for (int i = 0; i < m - 1; ++i)
      pre = pre->next;
    ListNode *cur = pre->next;
    for (int i = m; i < n; ++i) {
      ListNode *t = cur->next;
      cur->next = t->next;
      t->next = pre->next;
      pre->next = t;
    }
    return dummy->next;
  }
};

分割鏈表

思路：先找到一個大于或者等于給定值的節(jié)點，然后再逐個把小于他們的值放在前面。例如本例先找到4，然后再找到3，然后把小于3的值都放在其前面

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* partition(ListNode* head, int x) {
    ListNode *p=new ListNode(-1);
    p->next=head;
    ListNode *pre=p,*cur=head;
    while(pre->next&&pre->next->val<x)
      pre=pre->next;
    cur=pre;
    while(cur->next){
      if(cur->next->val<x){
        ListNode *tmp=cur->next;
        cur->next=tmp->next;
        tmp->next=pre->next;
        pre->next=tmp;
        pre=pre->next;
      }else{
        cur=cur->next;
      }
    }
    return p->next;
  }
};

逆序鏈表存儲數(shù)相加

思路：先建立一個p結(jié)點，然后將相加生成的新結(jié)點按順序放到p結(jié)點之后，然后再用一個新指針cur指向新鏈表的最后一位。設(shè)置一個進位計數(shù)res，當兩個結(jié)點值相加之后，可以用sum/10來表示進位，然后以sum%10來建立新的結(jié)點。最后需要注意的是最高位的進位問題，所以while結(jié)束后要，如果res為1，則再建一個值為1的結(jié)點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *p=new ListNode(-1),*cur=p;
    int res=0; 
    while(l1||l2){
      int val1=l1?l1->val:0;
      int val2=l2?l2->val:0;
      int sum=val1+val2+res;
      res=sum/10;
      cur->next=new ListNode(sum%10);
      cur=cur->next;
      if(l1)
        l1=l1->next;
      if(l2)
        l2=l2->next;
    }
    if(res)
      cur->next=new ListNode(1);
    return p->next;
  }
};

順序鏈表存儲相加

思路：這道題和第2題類似，但是鏈表是從前往后遍歷，加法卻要從最低位相加，所以可以考慮改用棧來存儲放進來的數(shù)據(jù)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    stack<int> s1, s2;
    while (l1) {
      s1.push(l1->val);
      l1 = l1->next;
    }
    while (l2) {
      s2.push(l2->val);
      l2 = l2->next;
    }
    int sum = 0;
    ListNode *res = new ListNode(0);
    while (!s1.empty() || !s2.empty()) {
      if (!s1.empty()) {
        sum += s1.top();
        s1.pop();
      }
      if (!s2.empty()) {
        sum += s2.top();
        s2.pop();
      }
      res->val = sum % 10;
      ListNode *cur = new ListNode(sum / 10);
      cur->next = res;
      res = cur;
      sum /= 10;
    }
    return res->val == 0 ? res->next : res;
  }
};

移除鏈表元素

思路：直接遞歸調(diào)用到鏈表末尾，然后回來，需要刪除的元素將鏈表next指針指向下一個元素即好。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* removeElements(ListNode* head, int val) {
    if(!head) return NULL;
    head->next=removeElements(head->next,val);
    return head->val==val?head->next:head;
  }
};

刪除排序鏈表中的重復元素

思路：遞歸查找，如果head的值存在且相等，那么while循環(huán)跳過后面所有值相等的結(jié)點，如果后面if還有值相等則繼續(xù)進行遞歸。如果最后到head的值不同后，返回到head即可。<這種方式比新建鏈表存儲時間負責度高很多>

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return head;
    if (head->next && head->val == head->next->val) {
      while (head->next && head->val == head->next->val) {
        head = head->next;
      }
      return deleteDuplicates(head->next);
    }
    head->next = deleteDuplicates(head->next);
    return head;
  }
};

刪除順序鏈表中的重復元素

思路：head結(jié)點的值和身后結(jié)點的值進行比較，如果值相同，則返回后面一個結(jié)點。最后回溯遞歸調(diào)用刪除重復結(jié)點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* deleteDuplicates(ListNode* head) {
    if(!head||!head->next) return head;
    head->next=deleteDuplicates(head->next);
    return (head->val==head->next->val)?head->next:head;
  }
};

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: