翻转链表I

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

1. implement iteratively

public class Solution {

    public ListNode reverseListiteratively(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        ListNode newhead = null;
        while(cur!=null){
            next = cur.next; //一旦cur node指向prev,原来的next就找不到了，因此需要提前保存next
            if(next == null)
                newhead = cur; //保存要返回的newhead的值
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return newhead;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arrays[] = {1,2,3,4,5};
        ListNode head = LinkTools.change_array_to_list(arrays);
        LinkTools.printList(new Solution().reverseListiteratively(head));
    }

}

2. implement recursively

public class Solution {
    public ListNode reverseListrecursively(ListNode head){
        if(head == null || head.next == null) //跳出循环的条件
            return head;
        
        ListNode cur = head; //保存当前的head结点
        ListNode newhead = reverseListrecursively(cur.next); 
        //假设此时除了head结点，其他链表已经翻转完成，新的head为newhead
        //此时当前的head还指向其next，需要进行翻转操作，让原来的next node指向自己，自己的next制空
        cur.next.next = cur;
        cur.next = null;
        //返回newhead
        return newhead;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arrays[] = {1,2,3,4,5};
        ListNode head = LinkTools.change_array_to_list(arrays);
        LinkTools.printList(new Solution().reverseListrecursively(head));
    }
}

翻转链表II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next==null || m==n)
            return head;
        //将链表分开为三个链表再重新进行连接，但要考虑m=1的特殊情况，加一个假的头结点是最方便的方法，省去许多特殊判断
        ListNode dummy = new ListNode(-1);
        ListNode part2_head = null;
        ListNode part2_end = null;  
        ListNode part3_head = null;
        ListNode part1_end = null;
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        for(int i = 1;i<m;i++){
            prev = prev.next;
            cur = cur.next;
        }
        part1_end = prev;
        part2_head = cur;
        part1_end.next = null; //暂时断链
        for(int i = m;i<n;i++){
            cur = cur.next;
        }
        part2_end = cur;
        part3_head = cur.next;
        part2_end.next = null;//暂时断链
        reverseListiteratively(part2_head);
        part1_end.next = part2_end;
        part2_head.next = part3_head;
        
        return dummy.next;   
    }

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false
Example 2:

Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?

 public boolean isPalindrome(ListNode head) {
         //关键在先找到链表的终点，采取快慢指针的方式
        if(head == null || head.next == null)
            return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null&&fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode list2_node = reverseListiteratively(slow.next);
        ListNode list1_node = head;
        while(list2_node!=null){
            if(list1_node.val!=list2_node.val){
                return false;
            }
            list1_node = list1_node.next;
            list2_node = list2_node.next;
        }
        return true;
    }

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

public ListNode sortList(ListNode head) {
        //最容易想到的应该是递归
        if(head == null || head.next == null)
            return head;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null&&fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode list2 = slow.next;
        ListNode list1 = head;
        slow.next = null;//断连成两个链表
        list1 = sortList(list1);
        list2 = sortList(list2);
        ListNode newhead = null;
        if(list1.val<list2.val){
            newhead = list1;
            list1 = list1.next;
        }
        else{
            newhead = list2;
            list2 = list2.next;
        }
        ListNode cur = newhead;
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
                
            }else{
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        cur.next = (list1==null)?list2:list1;
        return newhead;
    }