LeetCode：链表（二）

发表于 | 分类于

删除重复元素

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

1
2
3
4
5
6
7
8
Example 1:

Input: 1->1->2
Output: 1->2
Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

移除有序链表中的重复项需要定义个指针指向该链表的第一个元素，然后第一个元素和第二个元素比较，如果重复了，则删掉第二个元素，如果不重复，指针指向第二个元素。这样遍历完整个链表，则剩下的元素没有重复项。这道题比较简单。
C++参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head)return NULL;
        if(!head->next)return head;
         ListNode*pre=head;
        ListNode*cur=head->next;
        while(cur)
        {
            if(pre->val==cur->val)
            {
                ListNode*del=cur;
                cur=cur->next;
                pre->next=cur;
                delete del;
                del=NULL;
            }
             else{
                 cur=cur->next;
            pre=pre->next;
             }             
        }
        return head;
    }
};

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

1
2
3
4
5
6
7
8
Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:

Input: 1->1->1->2->3
Output: 2->3

和上面那道题不同的地方是这里要删除所有重复的节点，由于链表开头可能会有重复项，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。所以需要定义一个新的节点，然后链上原链表，然后定义一个前驱指针和一个现指针，每当前驱指针指向新建的节点，现指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把前驱指针的next指向下面那个不同的元素。如果现指针遍历的第一个元素就不相同，则把前驱指针向下移一位。C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *start = new ListNode(0);
        start->next = head;
        ListNode*pre=start;
        ListNode*cur=head;
        while(cur)
        {
            while(cur->next&&cur->val==cur->next->val)cur=cur->next;
            if(cur!=pre->next){pre->next=cur->next;cur=cur->next;} 
            else//注意这里是判断节点是否相等，不是判断节点值是否相等
            {
                cur=cur->next;
                pre=pre->next;
            }
        }
        return start->next;
    }
};

反转链表

206 Reverse Linked List

反转一个单链表。

1
2
3
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

这道题比较简单，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
       ListNode*pre=NULL;
        while(head)
        {
            ListNode*pnext=head->next;
            head->next=pre;
            pre=head;
            head=pnext;
        }
        return pre;
    }
};

92 Reverse Linked List II

这道题也是反转链表，只不过，这道题是反转固定区间的链表。将给定链表第m个节点到第n个节点的位置逆序，返回逆序后的链表。
给定M，N满足以下条件：
1≤M≤N≤列表的长度。

1
2
3
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

这道题比较难，需要考虑很多边界条件，感觉半小时内都不见得能做的完。下面给出一位网友的解法。如下图所示

基于上面的解法，代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* reverseBetween(ListNode* head, int m, int n) {
	 ListNode dummy(-1);
	 dummy.next = head;
	 ListNode*pre = &dummy;
	 for (int i = 0; i < m - 1; i++)
		 pre = pre->next;
	 ListNode*head2 = pre;
	 pre = pre->next;
	 for (size_t i = m; i < n; i++)
	 {
		 ListNode*cur = pre->next;
		 pre->next = cur->next;
		 cur->next = head2->next;
		 head2->next = cur;
		 cur = pre->next;
	 }
	 return dummy.next;
 }

这道题的关键在于我们要始终记住第m-1位的节点位置，这里使用的是head2存储，这个节点始终都保持不变。

断断续续的将剑指offer刷完了，开始对其中的每类题进行一个总结。链表是笔试中非常经典的一类数据结构，被问的概率巨大，因此在下面是对剑指offer上链表类的题目进行一个简单的讲解和总结。

从尾到头打印链表

题目描述：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
题目分析：这道题可以用栈来实现，每遍历一个节点就将这个节点值放入栈中。遍历完链表，在从栈顶开始逐个输出就行了。但这里我使用vector中的insert函数来实现。c++参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
       if(!head)return res;
        while(head)
        {
            res.insert(res.begin(),head->val);//每次都将节点值插在最前面
            head=head->next;
        }
        return res;
    }
};

合并两个有序链表

题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
题目分析：Step1.定义一个指向新链表的指针，暂且让它指向NULL； Step2.比较两个链表的头结点，让较小的头结点作为新链表的头结点； Step3.递归比较两个链表的其余节点，让较小的节点作为上一个新节点的后一个节点；
典型的递归实现，c++参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
   {
     if(!pHead1)  return pHead2;
       if(!pHead2) return pHead1;
       ListNode*pMerged=NULL;
       if(pHead1->val<pHead2->val)
       {
           pMerged=pHead1;
           pMerged->next=Merge(pHead1->next,pHead2);  
       }
       else
       {
            pMerged=pHead2;
           pMerged->next=Merge(pHead1,pHead2->next);
       }
       return pMerged;

链表倒数第k个节点

题目描述：输入一个链表，输出该链表中倒数第k个结点。
题目分析：这题使用快慢指针来解决。快慢指针都先指向头节点，先让快指针先走k-1步，然后两个指针同步走，步长相同，当快节点到达终点时，慢节点刚好指向倒数第k个节点。
思路清晰，比较简单，c++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
   if(!pListHead)return NULL;
       if(k<=0)return NULL;
       ListNode*fast=pListHead;
        ListNode*slow=pListHead;
       for(int i=0;i<k-1;i++)
       {
           if(fast->next)fast=fast->next;//这里要注意，防止k是大于链表长度，导致无效；
           else return NULL;
       }    
       while(fast->next)
       {
           fast=fast->next;
           slow=slow->next;
       }
       return slow;
   }

最后还有几个关于链表的问题，删除链表节点，单链表关于环的问题，这个我在上几篇博客有介绍，这里不再重复。总之，链表相关的题目相对来说还是比较简单。