链表定义及主函数

1、list.h文件

1、	#ifndef _LIST_H_  
2、	#define _LIST_H_  
3、	  
4、	struct ListNode  
5、	{  
6、	    int val;  
7、	    ListNode* next;  
8、	};  
9、	  
10、#endif 


2、main.cpp（省去链表排序代码）

1.	#include <iostream>  
2.	  
3.	using namespace std;  
4.	  
5.	#include "List.h"  
6.	  
7.	void InsertionSortList();  
8.	void SelectSortList();  
9.	  
10.	//构建链表头结点  
11.	ListNode* head = new ListNode;  
12.	  
13.	int main()  
14.	{  
15.	    head->next = NULL;  
16.	      
17.	    //对链表赋值  
18.	    for (int i = 0; i < 10; ++i)  
19.	    {  
20.	          
21.	        ListNode* p = new ListNode;  
22.	        cin >> p->val;  
23.	        p->next = head->next;  
24.	        head->next = p;  
25.	          
26.	    }  
27.	  
28.	    //这里填写链表排序函数，如下：
29.	    //InsertionSortList();  
30.	    SelectSortList();  
31.	  
32.	    ListNode* q = head->next;  
33.	    while (q)  
34.	    {  
35.	        cout << q->val << ' ';  
36.	        q = q->next;  
37.	    }  
38.	  
39.	    return 0;  
40.	}  



 

一、交换结点

1、直接插入排序

        假设排序规则为从小到大。

        左边的有序区为：head - pend的区域

        右边的无序区为：p – NULL的区域

        每次从head->next开始，tmp = head->next; 比较tmp->val与p->val和tmp与p的关系。

        pre为tmp的前缀节点。

        当tmp->val < p->val时，tmp、pre一直向后移；

        当tmp->val > p->val时，将tmp与p两结点交换；

        当tmp == p时，说明head – p为有序区，将pend = p。

        插入排序在链表应用中交换结点。



二、交换元素

1、选择排序

       假设排序规则由小到大。

       将待排序列分为有序序列与无序序列。

       每次在无序序列中找到最小的元素，将其与有序序列的最后一个值进行交换。

       选择排序在链表应用中交换元素而不交换节点。



2、快速排序

       单链表的快排序和数组的快排序基本思想相同，同样是基于划分，但是又有很大的不同：单链表不支持基于下标的访问。故算法中把待排序的链表拆分为2个子链表。

       为了简单起见，选择链表的第一个节点作为基准，然后进行比较，比基准小得节点放入左面的子链表，比基准大的放入右边的子链表。在对待排序链表扫描一遍之后，左边子链表的节点值都小于基准的值，右边子链表的值都大于基准的值，然后把基准插入到链表中，并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序，以提高性能。


       但是，由于单链表不能像数组那样随机存储，和数组的快排序相比较，还是有一些需要注意的细节：

       1、支点的选取，由于不能随机访问第K个元素，因此每次选择支点时可以取待排序那部分链表的头指针；
       2、遍历量表方式，由于不能从单链表的末尾向前遍历，因此使用两个指针分别向前向后遍历的策略失效。


       事实上，可以采用一趟遍历的方式将较小的元素放到单链表的左边。具体方法为：
       1)定义两个指针pslow，pfast，其中pslow指向单链表的头结点，pfast指向单链表头结点的下一个结点;
       2)使用pfast遍历单链表，每遇到一个比支点小的元素，就令pslow=pslow->next，然后和pslow进行数据交换。
       3)、交换数据方式，直接交换链表数据指针指向的部分，不必交换链表节点本身。

       链表快速排序描述来源：深入单链表的快速排序详解

题目描述：一个链表，奇数位升序偶数位降序，让链表变成升序的。比如：1 8 3 6 5 4 7 2 9，最后输出1 2 3 4 5 6 7 8 9。

分析：

这道题可以分成三步：

首先根据奇数位和偶数位拆分成两个链表。

然后对偶数链表进行反转。

最后将两个有序链表进行合并。
package com.Link;
public class 奇偶链表排序 {
	public static void main(String[] args) {		
		ListNode head = new ListNode(1);		
		ListNode node2 = new ListNode(8);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(6);
		ListNode node5 = new ListNode(5);
		ListNode node6 = new ListNode(4);
		ListNode node7 = new ListNode(7);
		ListNode node8 = new ListNode(2);
		ListNode node9 = new ListNode(9);
		head.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = node8;
		node8.next = node9;
		//printList(head);
		ListNode[] heads = splitList(head);
		//printList(heads[0]);
		//printList(heads[1]);
		ListNode reverseHead =reverseList(heads[1]);
		//printList(reverseHead);
		ListNode mergeHead =mergeLists(heads[0], reverseHead);
		printList(mergeHead);
	}
	// 按照奇偶位拆分成两个链表
	private static  ListNode[] splitList(ListNode head) {
		ListNode head1 = null;
		ListNode head2 = null;
		ListNode cur1 = null;
		ListNode cur2 = null;
		int count = 1;
		while (head != null) {
			if (count % 2 == 1) {
				if (cur1 != null) {
					cur1.next = head;
					cur1 = cur1.next;
				} else {
					cur1 = head;
					head1 = cur1;
				}
			} else {
				if (cur2 != null) {
					cur2.next = head;
					cur2 = cur2.next;
				} else {
					cur2 = head;
					head2 = cur2;
				}
			}
			head = head.next;
			++count;
		}
		// 跳出循环，要让最后两个末尾元素的下一个都指向null
		cur1.next = null;
		cur2.next = null;
		ListNode[] heads = new ListNode[]{head1, head2};
		return heads;
	}
	// 反转链表
	private static ListNode reverseList(ListNode head) {
		ListNode cur = head;
		ListNode pre = null;
		ListNode next = null;
		while (cur != null) {
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}
	// 合并两个有序链表
	private static ListNode mergeLists(ListNode head1, ListNode head2) {
		if (head1 == null && head2 == null) return null;		
		if (head1 == null || head2 == null) 
			return head1 == null ? head2 : head1;		
		ListNode first = new ListNode(-1);
		ListNode cur = first;
		while (head1 != null && head2 != null) {
			if (head1.val < head2.val) {
				cur.next = head1;
				head1 = head1.next;
			} else {
				cur.next = head2;
				head2 = head2.next;
			}
			cur = cur.next;
		}
		cur.next = head1 != null ? head1 : head2;
		return first.next;
	}

	// 初始化链表
	

	// 打印链表
	private static void printList(ListNode head) {
		if (head == null) return;
		ListNode cur = head;
		while (cur.next != null) {
			System.out.print(cur.val + "\t");
			cur = cur.next;
		}
		System.out.println(cur.val);
	}

	public static class ListNode {
		 int val;
		 ListNode next;
		 ListNode(int val) {
			this.val = val;
		}
	}
}