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;
}