合并两个有序的单链表 & 按照左右半区的方式重新组合单链表 & 单链表的选择排序

合并两个有序的单链表

题目：合并两个有序的单链表

《程序员代码面试指南》第29题 P88 难度：士★☆☆☆

本题很简单，只需要2个指针不停的遍历2个单链表即可。

哪个指针所指向的节点值小，就将其作为合并链表的下一个节点，并将该指针向后移动一个。

书上的做法感觉略有点复杂了。。

以下是牛客题解讨论的某个代码，感觉还不错：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] list1 = br.readLine().trim().split(" ");
        int m = Integer.parseInt(br.readLine().trim());
        String[] list2 = br.readLine().trim().split(" ");
        ListNode head1 = new ListNode(Integer.parseInt(list1[0]));
        ListNode head2 = new ListNode(Integer.parseInt(list2[0]));
        ListNode cur1 = head1, cur2 = head2;
        for(int i = 1; i < n; i++){
            cur1.next = new ListNode(Integer.parseInt(list1[i]));
            cur1 = cur1.next;
        }
        for(int i = 1; i < m; i++){
            cur2.next = new ListNode(Integer.parseInt(list2[i]));
            cur2 = cur2.next;
        }
        ListNode list = mergeLinkedList(head1, head2);
        while(list != null){
            System.out.print(list.val + " ");
            list = list.next;
        }
    }
    
    private static ListNode mergeLinkedList(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        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? head2: head1;
        return dummy.next;
    }
}

重点关注其mergeLinkedList方法。其中dummy的首个-1节点很有意思。这个-1节点其实是不存在的。最后无论head1还是head2节点值小，只需要返回dummy.next就行了，很方便。完美解决了不知道要用哪个链表的头结点作为合并链表的头结点，然后还要多加一层判断的问题（我的代码就是，很麻烦）。

另外书上代码如下，看看即可：

public Node merge(Node head1, Node head2) {
    if (head1 == null || head2 == null) {
      	return head1 != null ? head1 : head2;
    }
    Node head = head1.value < head2.value ? head1 : head2;
    Node cur1 = head == head1 ? head1 : head2;
    Node cur2 = head == head1 ? head2 : head1;
    Node pre = null;
    Node next = null;
    while (cur1 != null && cur2 != null) {
        if (cur1.value <= cur2.value) {
            pre = cur1;
            cur1 = cur1.next;
        } else {
            next = cur2.next;
            pre.next = cur2;
            cur2.next = cur1;
            pre = cur2;
            cur2 = next;
        }
    }
    pre.next = cur1 == null ? cur2 : cur1;
    return head;
}

按照左右半区的方式重新组合单链表

题目：按照左右半区的方式重新组合单链表

《程序员代码面试指南》第30题 P90 难度：士★☆☆☆

本题也很简单。书上的做法是遍历一遍找到左半区的最后一个节点mid后，将链表拆分下来（mid.next=null），然后依次作连接即可。

（注意奇偶差异以及左半区最后一个节点和右半区最后一或两个节点的连接）

代码如下：

public void relocate(Node head) {
	if (head == null || head.next == null) {
		return;
	}
	Node mid = head;
	Node right = head.next;
	while (right.next != null && right.next.next != null) {
		mid = mid.next;
		right = right.next.next;
	}
	right = mid.next;
	mid.next = null;
	mergeLR(head, right);
}

public void mergeLR(Node left, Node right) {
	Node next = null;
	while (left.next != null) {
		next = right.next;
		right.next = left.next;
		left.next = right;
		left = right.next;
		right = next;
	}
	left.next = right;
}

单链表的选择排序

题目：单链表的选择排序

《程序员代码面试指南》第26题 P84 难度：士★☆☆☆

有关选择排序的算法原理参见选择排序 | 菜鸟教程

本题我的做法复杂了。书上的思路是：

首先找到整个链表的最小值节点，作为新的头结点，记为newHead
每次在未排序的部分中找到最小值的节点，将其从未排序的链表中删除，然后把它连接到排好序部分的链表尾部
最后返回newHead

代码如下：

public static Node selectionSort(Node head) {
	Node tail = null; // 排序部分尾部
	Node cur = head; // 未排序部分头部
	Node smallPre = null; // 最小节点的前一个节点
	Node small = null; // 最小的节点
	while (cur != null) {
		small = cur;
		smallPre = getSmallestPreNode(cur);
		if (smallPre != null) {
			small = smallPre.next;
			smallPre.next = small.next;
		}
		cur = cur == small ? cur.next : cur;
		if (tail == null) {
			head = small;
		} else {
			tail.next = small;
		}
		tail = small;
	}
	return head;
}

public static Node getSmallestPreNode(Node head) {
	Node smallPre = null;
	Node small = head;
	Node pre = head;
	Node cur = head.next;
	while (cur != null) {
		if (cur.value < small.value) {
			smallPre = pre;
			small = cur;
		}
		pre = cur;
		cur = cur.next;
	}
	return smallPre;
}

算法题

合并两个有序的单链表 & 按照左右半区的方式重新组合单链表 & 单链表的选择排序