leetcode题解（链表类)

主要介绍链表在leetcode中的解题思路

链表，在节点间穿针引线

链表和数组都是线性结构，但是链表和数组的不同在于数组可以随机的对于数据进行访问。给出索引。可以以O(1)的时间复杂度迅速访问到该元素。
链表只能从头指针开始。

leetcode206.反转链表

思想

维护三个指针
- pre
- cur
- next

    // 时间复杂度: O(n)
    // 空间复杂度: O(1)
    class Solution {
    public:
 ListNode* reverseList(ListNode* head) {

     ListNode* pre = NULL;
     ListNode* cur = head;
     while( cur != NULL ){
  ListNode* next = cur->next;
  cur->next = pre;
  pre = cur;
  cur = next;
     }

     return pre;
 }
    };

相似问题

leetcode92 Reverse linked List II

反转一个链表从m到n的元素。

如对于链表 1->2->3->4->5->NULL, m = 2 , n = 4
则返回链表 1->4->3->2->5->NULL
- m和n超过链表范围怎么办？
- m > n 怎么办？

测试链表程序

写根据数组创建链表和打印链表两个函数

    /// linkedList Test Helper Functions
    ListNode* createlinkedList(int arr[], int n){

 if( n == 0 )
     return NULL;

 ListNode* head = new ListNode(arr[0]);
 ListNode* curNode = head;
 for( int i = 1 ; i < n ; i ++ ){
     curNode->next = new ListNode(arr[i]);
     curNode = curNode->next;
 }

 return head;
    }

    void printlinkedList(ListNode* head){

 ListNode* curNode = head;
 while( curNode != NULL ){
     cout << curNode->val << " -> ";
     curNode = curNode->next;
 }

 cout<<"NULL"<next;
     delete delNode;
 }

 return;
    }

main.cpp:

    int main(){

 int arr[] = {1, 2, 3, 4, 5};
 int n = sizeof(arr)/sizeof(int);

 ListNode* head = createlinkedList(arr, n);
 printlinkedList(head);

 ListNode* head2 = Solution().reverseList(head);
 printlinkedList(head2);

 deletelinkedList(head2);

 return 0;
    }

运行结果

1 -> 2 -> 3 -> 4 -> 5 -> NULL
5 -> 4 -> 3 -> 2 -> 1 -> NULL

相似题目 leetcode83 Remove Duplicates from Sorted List**

给出一个有序链表，删除其中所有重复元素，使得每个元素只保留一次。

如 1->1->2，返回1->2
如 1->1->2->3->3，返回1->2->3

leetcode86 Partition List

给出一个链表以及一个数x，将链表重新整理，使得小于x的元素在前；大于等于x的元素在后。

如 1->4->3->2->5->2，x=3
返回 1->2->2->4->3->5

leetcode328 Odd Even linked List

给出一个链表，将链表重新整理，使得所有索引为奇数的节点排在索引为偶数的节点前面。

如 1->2->3->4->5->NULL
返回 1->3->5->2->4->NULL
第一个节点的索引为1
奇数索引的节点和偶数索引的节点在重新整理后要保持相对顺序。

leetcode2 Add Two Numbers**

给出两个非空链表，表示两个非负整数。其中每一个整数的各位数字以逆序存储，返回这两个整数相加所代表的链表。

如 342 + 465 = 807
则给出 2->4->3 和 5->6->4，返回7->0->8

数字中是否有前置的0。（除0以外，没有前置0）
负数？

leetcode445 Add Two Numbers II**

给出两个非空链表，表示两个非负整数。其中每一个整数的各位数字以顺序存储，返回这两个整数相加所代表的链表。

如 342 + 465 = 807
则给出 3->4->2 和 4->6->5，返回8->0->7

提示
如果不允许修改输入的链表呢？
使用辅助数据结构

设立链表的虚拟头结点 leetcode203. 删除链表中的节点

该逻辑对删除最后一个元素依然适用
该逻辑对删除第一个元素不适用

不使用虚拟头结点代码

    // 不使用虚拟头结点
    class Solution {
    public:
 ListNode* removeElements(ListNode* head, int val) {

     while( head != NULL && head->val == val ){

  ListNode* node = head;
  head = head->next;
  delete node;
     }

     if( head == NULL )
  return head;

     ListNode* cur = head;
     while( cur->next != NULL ){

  if( cur->next->val == val ){
      ListNode* delNode = cur->next;
      cur->next = delNode->next;
      delete delNode;
      //delNode -> next = NULL;
  }
  else
      cur = cur->next;
     }

     return head;
 }
    };

虚拟头结点代码

    // 使用虚拟头结点
    class Solution {
    public:
 ListNode* removeElements(ListNode* head, int val) {

     ListNode* dummyHead = new ListNode(0);
     dummyHead->next = head;

     ListNode* cur = dummyHead;
     while( cur->next != NULL ){

  if( cur->next->val == val ){
      ListNode* delNode = cur->next;
      cur->next = delNode->next;
      delete delNode;
  }
  else
      cur = cur->next;
     }

     ListNode* retNode = dummyHead->next;
     delete dummyHead;

     return retNode;
 }
    };

相似问题 leetcode 82. Remove Duplicates from Sorted List II

给定一个有序链表，将其中有重复的元素全部删除。

*   如1->2->3->3->4->4->5，返回1->2->5
*   如1->1->1->2->3，返回2->3

leetcode 21. Merge Two Sorted Lists

merge两个有序的链表

复杂的链表操作 leetcode 24. 两两交换链表中的节点

步骤图解

核心在于创建几个指针预先保留。

代码实现

    class Solution {
    public:
 ListNode* swapPairs(ListNode* head) {

     ListNode* dummyHead = new ListNode(0);
     dummyHead->next = head;

     ListNode* p = dummyHead;
     while( p->next && p->next->next ){
  ListNode* node1 = p->next;
  ListNode* node2 = node1->next;
  ListNode* next = node2->next;
  node2->next = node1;
  node1->next = next;
  p->next = node2;
  p = node1;
     }

     ListNode* retHead = dummyHead->next;
     delete dummyHead;

     return retHead;
 }
    };

相似题目 leetcode 25. Reverse Nodes in k-Group

给定一个链表，每k个节点为一组，反转每一组的k个节点。k为正整数且小于等于链表长度。如果链表长度不是k的整数倍，剩余部分不需要进行反转。如： 1->2->3->4->5->NULL

若 k = 2，则结果为：2->1->4->3->5->NULL
若 k = 3，则结果为：3->2->1->4->5->NULL

leetcode 147. Insertion Sort List

为一个链表进行插入排序

leetcode 148. Sort List

写一个排序算法，用O(nlogn)的时间复杂度为一个链表进行排序

归并排序不需要使用数组索引：自底向上。

直接修改链表的节点 leetcode237. 删除链表中的节点

思路

采用赋值法
特殊情况改变节点的值来实现我们需要的功能。

    class Solution {
    public:
 void deleteNode(ListNode* node) {

     assert(node != NULL && node->next != NULL);

     node->val = node->next->val;
     ListNode* delNode = node->next;
     node->next = delNode->next;

     delete delNode;

     return;
 }
    };

双指针技术 leetcode 19. Remove Nth Node From End of List

注意

n从0计还是从1计
n不合法，负数或者大于链表长度如何处理（保证n合法）

解法1：先遍历一遍计算链表长度；再遍历一遍删除倒数第n个节点
遍历两遍链表。能否只遍历一遍链表？

代码实现


class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
 //初始为最后一个节点和倒数第n+1个节点，之间的间距为n+1;

 assert(n >= 0);

 ListNode* dummyNode = new ListNode(0);
 dummyNode -> next = head;
 ListNode* p = dummyNode;
 ListNode* q = dummyNode;

 for(int i = 0; i < n+1; i++){
     assert(q); 
     q = q -> next;
 }

 while(q != NULL){
     q = q -> next;
     p = p -> next;
 }

 ListNode* delNode = p -> next;
 p -> next = delNode -> next;
 delete delNode;

 ListNode* retNode = dummyNode -> next;
 delete dummyNode;
 return retNode;
    }
};

相似问题 leetcode 61. Rotate List

给定一个链表，让这个链表向右旋转k位。其中k为非负数。

如：1->2->3->4->5->NULL, k = 2
第一次旋转：5->1->2->3->4->NULL
第二次旋转：4->5->1->2->3->NULL

leetcode 143. Reorder List

给定一个链表 L(0) -> L(1) -> L(2) -> … -> L(n-1) -> L(n)
将其变为 L(0) -> L(n) -> L(1) -> L(n-1) -> L(2) -> L(n-2)…
的形式

注意

链表无法随机访问数据，如何获得中间的元素？
两次遍历？一次遍历？

leetcode234. Palindrome linked List

给一个链表，判断这个链表是否为回文（正看反看）链表。

注意

能否使用O(1)的空间复杂度解决问题？

原创始发于慕课网

leetcode题解（链表类)

C/C++/C#相关栏目本月热门文章