Java-数据结构-链表＜三＞

承接上文 Java-数据结构-链表＜一＞

               Java-数据结构-链表＜二＞

一. 链表简单介绍 

        见 Java-数据结构-链表＜一＞

 

二. 链表的代码实现

        见 Java-数据结构-链表＜一＞

 

三. leetcode&牛客实例

 

1-6 见 Java-数据结构-链表＜一＞

7-13 见Java-数据结构-链表＜二＞

14. leetcode2 两数相加

        给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyhead = new ListNode(0);
        ListNode cur = dummyhead;
        int carry = 0;
        while(l1 != null || l2 != null){
            int L1_val = l1 == null ? 0 : l1.val;
            int L2_val = l2 == null ? 0 : l2.val;
            int sum = L1_val+L2_val+carry;
 
            carry = sum/10;
            sum = sum%10;
 
            cur.next = new ListNode(sum);
            cur = cur.next;
 
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
               l2 = l2.next;
            }
        }
        if(carry != 0){
            cur.next = new ListNode(1);
        }
        return dummyhead.next;
    }
}

15. leetcode24 两两相交链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4]
输出：[2,1,4,3]

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

16. leetcode23 合并k个升序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

暴力

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List list = new ArrayList<>();
        for(int i = 0; i< lists.length; i++){
            ListNode temp = lists[i];
            while(temp != null){
                list.add(temp.val);
                temp = temp.next;
            }
        }
        ListNode head = new ListNode(0); 
        ListNode first = head;
        Collections.sort(list);
        for(int i = 0; i < list.size(); i++){
            first.next = new ListNode(list.get(i));
            first = first.next;
        }
        return head.next;
    }
}

优先队列

class Solution {
    class heap implements Comparator{
        public int compare(ListNode o1, ListNode o2){
            return o1.val - o2.val;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue list = new PriorityQueue<>(new heap());
        for(ListNode cur : lists){
            while(cur != null){
                list.add(cur);
                cur = cur.next;
            }
        }
        ListNode dummyhead = new ListNode(0);
        ListNode cur = dummyhead;
        while(!list.isEmpty()){
            cur.next = list.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummyhead.next;
    }
}

两两合并【1】

class Solution {
	public ListNode mergeKLists(ListNode[] lists) {
		if(lists==null || lists.length==0) {
			return null;
		}
		//将lists[0]作为最终合并的链表，然后将list[0]和lists[1]合并成lists[0-1]
		//再将lists[0-1]和lists[2]合并，如此反复最终lists[0]就是最终结果
		ListNode res = lists[0];
		for(int i=1;i
			res = merge(res,lists[i]);
		}
		return res;
	}
	
	//合并两个有序链表
	private ListNode merge(ListNode a, ListNode b) {
		if(a==null || b==null) {
			return (a==null) ? b : a;
		}
		if(a.val<=b.val) {
			a.next = merge(a.next,b);
			return a;
		} else {
			b.next = merge(a,b.next);
			return b;
		}
	}
}

分治【1】

class Solution {
	public ListNode mergeKLists(ListNode[] lists) {
		if(lists==null || lists.length==0) {
			return null;
		}
		return helper(lists,0,lists.length-1);
	}
	
	//通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并
	//通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程
	private ListNode helper(ListNode[] lists, int begin, int end) {
		if(begin==end) {
			return lists[begin];
		}
		int mid = begin+(end-begin)/2;
		ListNode left = helper(lists,begin,mid);
		ListNode right = helper(lists,mid+1,end);
		return merge(left,right);
	}
	
	//合并两个有序链表
	private ListNode merge(ListNode a, ListNode b) {
		if(a==null || b==null) {
			return (a==null) ? b : a;
		}
		if(a.val<=b.val) {
			a.next = merge(a.next,b);
			return a;
		} else {
			b.next = merge(a,b.next);
			return b;
		}
	}
}

17. leetcode25 k个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

栈

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        Deque stack = new ArrayDeque();
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (true) {
            int count = 0;
            ListNode tmp = head;
            while (tmp != null && count < k) {
                stack.add(tmp);
                tmp = tmp.next;
                count++;
            }
            if (count != k) {
                p.next = head;
                break;
            }
            while (!stack.isEmpty()){
                p.next = stack.pollLast();
                p = p.next;
            }
            p.next = tmp;
            head = tmp;
        }
        return dummy.next;
    }
}

 暴力

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
 
    ListNode pre = dummy;
    ListNode end = dummy;
 
    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) end = end.next;
        if (end == null) break;
        ListNode start = pre.next;
        ListNode next = end.next;
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
        pre = start;
 
        end = pre;
    }
    return dummy.next;
}
 
private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

 

参考自：

【1】leetcode 王尼玛 四种解法+多图演示 23. 合并K个排序链表

【2】leetcode  画手大鹏 画解算法：24. 两两交换链表中的节点

【3】leetcode 房建斌学算法 图解k个一组翻转链表 

【4】leetcode powcai k 个一组翻转链表 ​​​​​​​