关于链表的一些操作备忘

定义链表结构体

struct ListNode { int val; ListNode* next; };

链表初始化

ListNode* l1 = new ListNode; l1->next = NULL; ListNode* l2 = new ListNode; l2->next = NULL;

求链表长度

int length(ListNode* head) { int len = 0; ListNode* tmp = head; while (tmp != NULL) { len++; tmp = tmp->next; } return len; }

输入链表（借鉴，略有改动）

void createList(ListNode* pHead) { ListNode* p = pHead; int inputVal; cin >> inputVal; while(inputVal!=-1){ ListNode* pNewNode = new ListNode; pNewNode->val = inputVal; // 将新节点的值赋值为i pNewNode->next = NULL; p->next = pNewNode; // 上一个节点指向这个新建立的节点 p = pNewNode; // p节点指向这个新的节点 cin >> inputVal; } }

输出链表（借鉴，略有改动）

void printListNode(ListNode* head) { ListNode* temp = head; while (temp) { cout << temp->val << " "; temp = temp->next; } cout << endl; }

尾插法 （在链表的尾部 tail 处插入新元素9）

tail -> next = new ListNode; tail -> next -> val = 9; tail -> next ->next = NULL;

· · · 整体代码 （供参考如何使用） （适用于leetcode 2.两数相加）

#include <iostream> using namespace std; struct ListNode { int val; ListNode* next; }; void createList(ListNode* pHead) { ListNode* p = pHead; int inputVal; cin >> inputVal; while(inputVal!=-1){ ListNode* pNewNode = new ListNode; pNewNode->val = inputVal; // 将新节点的值赋值为i pNewNode->next = NULL; p->next = pNewNode; // 上一个节点指向这个新建立的节点 p = pNewNode; // p节点指向这个新的节点 cin >> inputVal; } } int length(ListNode* head) { int len = 0; ListNode* tmp = head; while (tmp != NULL) { len++; tmp = tmp->next; } return len; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* tmp; int len1 = length(l1),len2 = length(l2); int flag = 0; if (len1 >= len2) { tmp = l1; for (int i = 0; i < len1; i++) { if (i < len2) { l1->val += l2->val; l2 = l2->next; } l1->val += flag; flag = l1->val / 10; l1->val %= 10; if(i==len1-1 && flag){ l1 -> next = new ListNode; l1 -> next -> val = 1; l1 -> next ->next = NULL; } l1 = l1->next; } } else { tmp = l2; for (int i = 0; i < len2; i++) { if (i < len1) { l2->val += l1->val; l1 = l1->next; } l2->val += flag; flag = l2->val / 10; l2->val %= 10; if (i == len2 - 1 && flag) { l2->next = new ListNode; l2->next->val = 1; l2->next->next = NULL; } l2 = l2->next; } } return tmp; } void printListNode(ListNode* head) { ListNode* temp = head; while (temp) { cout << temp->val << " "; temp = temp->next; } cout << endl; } int main() { ListNode* l1 = new ListNode; l1->next = NULL; ListNode* l2 = new ListNode; l2->next = NULL; createList(l1); createList(l2); printListNode(l1->next); printListNode(l2->next); printListNode(addTwoNumbers(l1->next, l2->next)); }