c++练习(10)：链表练习

• 单向链表(singly linked list),每个节点有一个next指针指向后一个节点，还有一个成员变量用来存储数值。
• 双向链表(Doubly linked List),还有一个prev指针指向前一个节点。
  Search:O(n),Del,Add:O(1)
  

题目1：从链表中删除重复的元素(1)

给一个排序好的链表，删除链表中重复的元素，使得链表中每个元素都唯一

class Solution
{
	ListNode* deleteDuplicates(ListNode *head)
	{
		if(head==NULL)
		{
			return NULL;
		}
		ListNode* node=head;
		while(node ->next !=NULL)
		{
			if(node->val ==node->next->val)
			{
				ListNode *temp=node->next;
				node->next =node->next->next;
				delete temp;
			}
			else
			{
				node=node->next;
			}
		}
	}
	return head;
}
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

Dummy Node 技巧

dummy node是一个虚拟的节点，dummy node 在head之前并指向head:只要涉及操作head节点，当头节点操作不确定的时候，不妨创建dummy node;

ListNode *dummy=new ListNode(0);
dummy ->next=head;
1
2

题目1：从链表中删除重复的元素(2)

给一个排序好的链表，删除有重复元素的所有节点，只保留原来只有唯一元素的节点。
例如：
给定1->2->3->3->4->4->5，return 1->2->5
给定 1->1->1->2->3, return 2->3

class Solution
{
public:
	ListNode* deleteDuplicates(ListNode* head)
	{
		if(head == NULL) return NULL;
		ListNode *dummy=new ListNode(0);
		dummy->next = head;
		ListNode *node=dummy;  //创建一个用于遍历的节点
		while(node->next !=NULL && node->next->next !=NULL)
		{
			int val_prev=node ->next->val;
			while(node ->next !=NULL && val_prev ==node->next->val )
			{
				ListNode *temp=node->next;
				node ->next = node->next->next;
				delete temp;
			}
			else
			{
				node =node->next;
			}
		}
	}
	return dummy->next;
}
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

题目2：链表分割

给定一个链表和一个数值，写一个函数重新排序链表，使得小于给定值的节点排在链表的左边,大于给点值的节点排在链表右侧。
思路: 链表的头节点是否为null 不确定,一般涉及head节点的操作，就需要创建一个dummynode
引入左右两个dummynode

class Solution
{
public:
	ListNode* partition(ListNode* head,int x)
	{
		ListNode* leftDummy= new ListNode(0);
		ListNode* left=leftDummy;
		ListNode* rightDummy =new ListNode(0);
		ListNode* right=rightDummy;
		ListNode  node=head;
		while(node !=NULL)  //没有到尾节点
		{
			if(node ->val <x)
			{
				// 
				left->next=node;
				left =left->next;
			}
			else
			{
				// >x的节点 存在右链表
				right->next=node;
				right=right->next;
			}
			node=node->next;
		}
		right->next =NULL;
		left ->next=rightDummy->next;
		
		return leftDummy->next;
	}
}
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

追赶指针技巧

追赶指针是一种快慢指针，每次移动步长较大的为快指针，较小的为慢指针，一般用在单链表中。

对于寻找list某个特定位置的问题，不妨用两个变量chaser与runner，以不同的速度遍历list,找到目标位置: ListNode *charser=head, *runner=head,并且可以用一个简单的小test case来验证(例如长度为4和5的list)

题目1：找到链表的中间节点

解题分析:寻找特定位置,runner以两倍速前进,chaser 一倍速，当runner到达tail时，chaser即为所求解。

/**
     * 中间节点在左半边  节点个数为奇数
     *
     * @param head
     * @return
     */
    public Node getMiddleNodeLeft(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 中间节点右半边   节点个数为偶数
     *
     * @param head
     * @return
     */
    public Node getMiddleNodeRight(Node head) {

        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
	
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

详情参考博客：获取链表的中间节点的两种方法

题目2：找到单向链表中倒数第k个节点

解题分析: 与题目1类似，runner和chaser以相同倍速前进，但runner提前k步出发。

List *findkthtoLast(ListNode *head,int k)
{
	ListNode *runner=head;
	ListNode *chaser=head;
	if(head == NULL || k<0)
		return NULL;
	for(int i=0;i<k;i++)
	 runner=runner->next;
	
	if(runner == NULL)
		return NULL;
	
	while(runner ->next!=NULL)
	{
		chaser=chaser->next;
		runner=runner->next;
	}	
	return chaser;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19