[数据结构与算法]LeetCode-链表

概念

链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。

LeetCode中链表的定义如下：

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

链表有两个操作的小技巧：

• 建立一个虚拟节点dummy node，使其指向当前链表的头结点，最终返回dummy.next;
• 删除操作时，尽量处理当前节点的下一个节点而非当前节点本身。

下面列举一些LeetCode上常见链表题目，可以按照顺序刷题。

算法题（题目序号为LeetCode题目序号）

206. 翻转链表

递归写法：首先找到链表中的最后一个节点，然后再翻转

    /**
     * 递归写法 先找到最后一个节点然后反向反转
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }

非递归写法：只需记录当前链表节点和前一个节点，然后把当前链表节点指向前一个节点。

    /**
     * 非递归写法
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
         // 1.迭代写法
         if(head == null) {
             return head;
         }
         ListNode pre = null,next = null;
         while(head != null) {
             next = head.next;
             head.next = pre;
             pre = head;
             head = next;
         }

         return pre;
    }

21.合并两个有序链表

递归方式：

    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
         // 递归
         if(l1 == null){
             return l2;
         }
         if(l2 == null){
             return l1;
         }
         if(l1.val > l2.val) {
             l2.next = mergeTwoLists(l1,l2.next);
             return l2;
         }else {
             l1.next = mergeTwoLists(l1.next,l2);
             return l1;
         }
    }

非递归方式：

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0),cur = head;
        while(l1 != null && l2 != null) {
            if(l1.val > l2.val) {
                cur.next = l2;
                l2 = l2.next;
            }else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ?l2:l1;
        return head.next;
    }

234.判断链表是否回文

主要思路是：先快慢指针找到链表中点，将后半段链表翻转，判断与前半段是否相等。

    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        // 先快慢指针找到链表中点，将后半段链表翻转，判断与前半段是否相等
        ListNode slow = head,fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 翻转后半段链表
        slow.next = reverseList(slow.next);
        slow = slow.next;
        // 比较两部分链表是否相等
        while(slow != null){
            if(head.val != slow.val) {
                return false;
            }
            slow = slow.next;
            head = head.next;
        }

        return true;
    }
    // 翻转链表
    public ListNode reverseList(ListNode node) {
        ListNode pre = null,next;
        while(node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

83.删除链表中的重复元素

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        // 删除链表
        ListNode node = head;
        while(node != null) {
            if(node.next != null && node.val == node.next.val) {
                node.next = node.next.next;
            }else {
                node = node.next;
            }
        }
        return head;
    }

19.删除链表中倒数第N个节点

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 快慢指针找到链表中点
        ListNode slow = head,fast = head;
        while(n-->0){
            if(fast.next != null) {
                fast = fast.next;
            }else {
                return head.next;
            }
        }
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // slow 为当前中点
        slow.next = slow.next.next;
        return head;
    }

148.排序链表

做这题之前，需要了解归并排序的写法，我在这里提供一下：

    public static void main(String[] args) {
        int[] arr = {4,5,6,9,7,1,2,3,8};
        new Digui().sort(arr,0,arr.length-1);
    }
    public void sort(int[] arr,int left,int right) {
        if(left >= right){
            return;
        }
        int mid = left + (right - left) /2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        merge(arr,left,mid+1,right);
    }
        /**
     * 合并
     * @param arr    数组
     * @param lStart l开始
     * @param rStart r开始
     * @param rEnd   r结束
     */
    public void merge(int[] arr,int lStart,int rStart,int rEnd) {
        int mid = rStart-1;
        int i = lStart;
        int j = rStart;
        int k = 0;
        int[] temp = new int[rEnd-lStart+1];
        while (i <= mid && j <= rEnd){
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            }else {
                temp[k++] = arr[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= rEnd) {
            temp[k++] = arr[j++];
        }

        for (int l = 0; l < temp.length; l++) {
            arr[lStart+l] = temp[l];
        }
    }

思路：先通过快慢指针找到链表中点，从中点处断开链表，然后左右归并两个链表。

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        //  快慢指针找到链表中点
        ListNode slow = head,fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 得到中点
        ListNode rStart = slow.next;
        // 断开链表
        slow.next = null;
        // 对中点左右的链表，进行归并排序
        ListNode left = sortList(head);
        ListNode right = sortList(rStart);
        return merge(left,right);
    }

    // 归并两个有序链表
    public ListNode merge(ListNode left,ListNode right) {
        // if(right.next == null) {
        //     return left;
        // }
        ListNode head = new ListNode(-1),node = head;
        while(left != null && right != null) {
            if(left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }

        while(left != null) {
            node.next = left;
            left = left.next;
            node = node.next;
        }

        while(right != null) {
            node.next = right;
            right = right.next;
            node = node.next;
        }

        return head.next;
    }