【剑指offer】——合并两个排序的链表

淩亂°似流年 2023-08-17 16:50 182阅读 0赞

## 题目描述 ##

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：

分别比较两个链表listNode1和listNode2的头指针位置的元素，比较后较小的数添加到新的链表中，并且指针后移一位。

（emmm..这道题我卡在了往新链表末尾，添加节点上o(ﾟДﾟ)っ！）

上代码

public static  ListNode Merge(ListNode list1,ListNode list2) {
            ListNode listHead1 = list1;
            ListNode listHead2 = list2;
            
            ListNode current = null;
            while(listHead1 != null && listHead2 !=null){
            	ListNode add  = null;
            	if(listHead1.val >= listHead2.val) {  //如果当前链表1的头结点 >= 链表2的头结点 
            		add = new ListNode(listHead2.val);
            		listHead2 = listHead2.next;
            	}else if(listHead1.val < listHead2.val) {
            		add = new ListNode(listHead1.val);
            		listHead1 = listHead1.next;
            	}
            	if(current == null){
            		current = add;
                }else {
                	ListNode tmp = current;
            	    while(tmp.next!=null){
            	        tmp=tmp.next;
            	    }
            	    tmp.next = add;
                }
            }
            ListNode add = null;
            if(listHead1 != null ) {
            	add = listHead1;
            }else {
            	add = listHead2;
            }
            
            if(current == null) {
            	return add;
            }else {
            	ListNode tmp = current;
        	    while(tmp.next!=null){
        	        tmp=tmp.next;
        	    }
        	    tmp.next = add;
            }
    		return current;
        }
    public static void main(String[] args) {
    //		ListNode listNode1 = new ListNode(1);
    //		listNode1.next = new ListNode(2);
    //		listNode1.next.next = new ListNode(3);
    //		listNode1.next.next.next = new ListNode(4);
    //		listNode1.next.next.next.next = new ListNode(5);
    //		listNode1.next.next.next.next.next = new ListNode(6);
    		
    		ListNode listNode1 = null;
    		ListNode listNode2 = new ListNode(2);
    		listNode2.next = new ListNode(4);
    		listNode2.next.next = new ListNode(6);
    		listNode2.next.next.next = new ListNode(8);
    		listNode2.next.next.next.next = new ListNode(10);
    		listNode2.next.next.next.next.next = new ListNode(12);
    	    System.out.println(Merge(listNode1,listNode2));
    }

卡着的地方总结一下

ListNode current = null;    //保存当前链表的指针
                if(current == null){
            		current = add;          //如果当前链表为空，就添加第一个元素
                }else {
                	ListNode tmp = current;    //用于遍历循环，找到链表末尾位置的指针tmp
            	    while(tmp.next!=null){     
            	        tmp=tmp.next;
            	    }
            	    tmp.next = add;            //末尾已找到添加元素，而此时tmp对原本的current并没有什么影响，current指针还是指向了原本链表的头部
    
                }

（我就是没用利用tmp指针，一直用current指针来遍历，导致寻找到末尾位置时，前面的就丢了。。。惭愧）