链表题思路总结

语言: CN / TW / HK

数据结构——链表

最近刷了一些关于链表的题目,所以也在此进行一下总结链表数据结构中主要会用到的一些方法。

头插法

在链表的题目中,经常会用到头插法,具体的做法就是新建一个指针指向一块空白的内存,然后将原指针指向的链表,一个个插入到我们新建的指针后面。

Listnode* newhead = new Listnode();
while(l1){
  Listnode* temp = l1->next;
  l1->next = newhead->next;
  newhead->next = l1;
  l1 = temp;
}
复制代码

上面的代码是对头插法的一个简单步骤总结,最后我们会获得原链表的倒序,不过需要注意的是,此时newhead指向的是我们新建的内存空间,而不是我们想要的原链表的最后一块,如果要使newhead直接指向原链表最后一块,只要简单的使它等于自身的next即可。

newhead = newhead->next;
复制代码

用到头插法的链表题有206反转链表、445链表求和,这些题目都要求了从末位到首位进行计算,所以很容易就能想到用头插法。

递归法

递归法无论是在链表题中,还是在其他的数据结构题目中,都是一种很好的解题思路,因为递归法使我们只需要将思路局限于部分,就可以解决整体的问题,所以也是算法题的万能解法了。做递归的题目需要思考以下几个步骤,递归的终止条件是什么,递归每一步需要进行什么处理,递归需要对上一层返回什么值。

拿21题合并两个有序链表来举例,题目要求对两个升序的链表进行合并为一条链表,这条链表中同时也保持升序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr)return l2;
        if(l2==nullptr)return l1;
        if(l1->val<l2->val){
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l2->next,l1);
            return l2;
        }
    }
};
复制代码

我们只关注传入函数的两个节点l1和l2,那么在递归过程中,我们需要做的无非就是对这两个节点进行排序,很容易想到比较它们的值,比较完值之后,我们不能把val大的节点直接放在val小的节点之后,因为还不确定val大的节点是否小于val小的节点的next的val,所以就需要递归调用这个函数,再将next与val大的节点进行比较,最后返回的就是这个val小的节点。那么终止条件应该是什么呢?可以想到比到最后肯定有l1或l2为nullptr的情况,所以我们只需要在一方为nullptr的情况下返回另外一个即可,不可能两者都为nullptr,因为这种情况在上一层函数中就已经应该返回了。

快慢指针法

快慢指针法适用于我们要找链表中的特殊位置的时候,比如说我们需要找链表中倒数第二个位置,就可以让快指针先走2步,然后慢指针再指向头部,接下来两者一起向后走,等到快指针的next指向nullptr时,慢指针的next也就指向倒数第二节点位置,如下面的代码所示。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head,*slow = head;
        while(--n>=0){
            fast = fast->next;
        }
        if(fast==nullptr)return head->next;
        while(fast->next!=nullptr){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};
复制代码

遍历法

剩下比较常规的方法就是遍历法,对于一条链表按照特定的顺序进行遍历,在这个过程中对链表进行处理,得到最终需要的链表顺序,这种题目一般都是对链表直接进行处理,不需要新建节点。

如下面的328奇偶链表题,题目要求将奇数节点连在一起,偶数节点连在一起,然后再在奇数节点的末尾连上偶数节点,还是很容易想到使用遍历方法,分别处理奇数节点和偶数节点的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            return head;
        }
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenhead = head->next;
        while(even!=nullptr&&even->next!=nullptr){
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenhead;
        return head;
    }
};
复制代码
分享到: