脚本宝典收集整理的这篇文章主要介绍了合并两个有序的单链表 & 按照左右半区的方式重新组合单链表 & 单链表的选择排序，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

合并两个有序的单链表

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

《程序员代码面试指南》第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 &amp;& 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;
}

脚本宝典总结

以上是脚本宝典为你收集整理的合并两个有序的单链表 & 按照左右半区的方式重新组合单链表 & 单链表的选择排序全部内容，希望文章能够帮你解决合并两个有序的单链表 & 按照左右半区的方式重新组合单链表 & 单链表的选择排序所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。