leetcode - 链表

链表专题训练。
1、反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode temp = head.next;
        head.next = null;
        ListNode next = null;
        while(temp != null) {
            next = temp.next;
            temp.next = head;
            head = temp;
            temp = next;
        }
        return head;
    }
}

2、反转链表2
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

  public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode start = head;
        ListNode front = null;
        int count = 1;
        while(count != m) {
            if(start != null) {
                front = start;
                start = start.next;   
            }
            count++;
        }
        ListNode temp = start.next;
        ListNode need = start;
        start.next = null;
        ListNode next;
        while(temp != null && count != n) {
            next = temp.next;
            temp.next = start;
            if(front != null) {
                front.next = temp;
            }
            start = temp;
            temp = next;
            count++;
        }
        if(temp != null) {
            need.next = temp;
        }
        if(m == 1) head = start;
        return head;
    }

3、对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4

class Solution {
    public ListNode insertionSortList(ListNode head) {
           if(head == null) return head;
        if(head.next == null) return head;
        ListNode current = head.next;
        head.next = null;
        ListNode next = current.next;
        if(current.val > head.val) {
            head.next = current;
            current.next = null;
            current = next;
            next = next.next;
        }
        while (current != null || next != null) {
            ListNode temp = findTargetPosition(current, head);
            head = temp == null ? head : temp;
            current = next;
            if(current != null) {
                next = next.next;
            }
        }
        return head;
    }

    public ListNode findTargetPosition(ListNode current, ListNode head) {
        ListNode node = head;
        ListNode front = head;
        while (node != null) {
            if (node == head && node.val >= current.val) {
                current.next = node;
                node = current;
                break;
            } else if (node != head && node.val >= current.val) {
                current.next = front.next;
                front.next = current;
                node = head;
                break;
            } else {
                front = node;
                node = node.next;
                if(node == null) {
                    front.next = current;
                    current.next = null;
                }
            }
        }
        return node;
    }
}

4、合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

public class MergeTwoLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
        ListNode a = l1;
        ListNode b = l2;
        ListNode temp = new ListNode(0);
        ListNode root = temp;
        while(a != null || b!= null) {
            int x = b == null ? Integer.MAX_VALUE : b.val;
            int y = a == null ? Integer.MAX_VALUE : a.val;
            if(y > x) {
                temp.next = b;
                b = b.next;
                temp = temp.next;
            } else {
                temp.next = a;
                a = a.next;
                temp = temp.next;
            }
        }
        return root.next;
    }
}

5、合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例：
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        ArrayList<ListNode> arrayList = new ArrayList<>();
        ListNode root = new ListNode(0);
        ListNode temp = root;
        for (ListNode elem: lists) {
            while(elem != null) {
                arrayList.add(elem);
                elem = elem.next;
            }
        }
        Collections.sort(arrayList, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode elem: arrayList) {
            temp.next = elem;
            temp = temp.next;
        }
        return root.next;
    }
}

6、K个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
> 示例 :
> 给定这个链表：1->2->3->4->5
> 当 k = 2 时，应当返回: 2->1->4->3->5
> 当 k = 3 时，应当返回: 3->2->1->4->5
> 说明 :
> 你的算法只能使用常数的额外空间。
> 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

public class ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        int t = k;
        int length = getLength(head);
        int count = length / k;
        int mod = length % k;
        ListNode temp = head;
        ListNode next = head.next;
        ListNode start = new ListNode(0);
        ListNode root = start;
        while (count !=0) {
            if(t!=0) {
                temp.next = start.next;
                start.next = temp;
                temp = next;
                if (temp != null) next = next.next;
                t--;
            } else {
                t = k;
                count--;
                start = head;
                head = temp;
            }
        }
        if(mod != 0) {
            while (temp != null){
                start.next = temp;
                temp = temp.next;
                start = start.next;
            }
        }
        return root.next;
    }

    public int getLength(ListNode head) {
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }
}