ListNode詳解

一、ListNode的概念

ListNode是鏈表的基本單元，它包含了一個值和一個指向下一個節點的指針。其中，鏈表是由一系列的節點組成，每個節點都包含了當前節點的值和指向下一個節點的指針。

鏈表通常分為單向鏈表、雙向鏈表和循環鏈表等不同類型，而ListNode則是這些鏈表中最基本的節點類型。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

二、ListNode的操作

1、創建ListNode

ListNode的創建可以通過new關鍵字動態分配內存來實現。下面代碼實現了創建一個包含3個節點的鏈表。

ListNode* createList() {
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    n1->next = n2;
    n2->next = n3;
    n3->next = NULL;
    return n1;
}

2、遍歷ListNode

遍歷ListNode需要循環處理每個節點，從頭節點開始，依次訪問每個節點的值。

void traverseList(ListNode* head) {
    ListNode* p = head;
    while(p) {
        cout<<p->val<<" ";
        p = p->next;
    }
}

3、插入節點

在ListNode中插入一個新節點，需要將新節點插入到指定位置。可以通過三個指針來實現：pre、cur、next，其中pre指向當前位置的前一個節點，cur指向當前位置，next指向當前位置的下一個節點。

void insertNode(ListNode* head, int pos, int val) {
    ListNode* p = head;
    ListNode* pre = NULL;
    for(int i=0; i<pos; i++) {
        pre = p;
        p = p->next;
    }
    ListNode* newNode = new ListNode(val);
    pre->next = newNode;
    newNode->next = p;
}

4、刪除節點

刪除ListNode中的一個節點，需要將該節點的前一個節點pre指向該節點的下一個節點next。

void deleteNode(ListNode* head, int val) {
    ListNode* p = head;
    ListNode* pre = NULL;
    while(p) {
        if(p->val == val) {
            if(pre) {
                pre->next = p->next;
            } else {
                head = p->next;
            }
            delete p;
            break;
        }
        pre = p;
        p = p->next;
    }
}

三、ListNode的應用

1、反轉鏈表

反轉一個單向鏈表可以採用三個指針，按照當前節點、前一個節點和下一個節點的順序調整，不斷向後移動，直到遍歷完整個鏈表。

ListNode* reverseList(ListNode* head) {
    ListNode* p = head;
    ListNode* pre = NULL;
    while(p) {
        ListNode* next = p->next;
        p->next = pre;
        pre = p;
        p = next;
    }
    return pre;
}

2、鏈表求和

給定兩個鏈表，每個鏈表代表一個非負整數，每個節點代表整數的一位。將這兩個整數相加，並以鏈表的形式返回結果。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* p = dummy;
    int sum = 0;
    while(l1 || l2 || sum) {
        if(l1) {
            sum += l1->val;
            l1 = l1->next;
        }
        if(l2) {
            sum += l2->val;
            l2 = l2->next;
        }
        p->next = new ListNode(sum % 10);
        sum /= 10;
        p = p->next;
    }
    return dummy->next;
}

3、環形鏈表

判斷給定的鏈表是否有環，並返回第一個進入環的節點。可以使用快慢指針法。慢指針每次向後移動一步，快指針每次向後移動兩步。如果鏈表存在環，則兩個指針一定會相遇，此時將其中的一個指針移回到頭節點，然後兩個指針每次向後移動一步，相遇的位置即為環的起點。

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