链表的常用操作

单链表的定义

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

单链表的常用操作

反转链表（逆序）

/** * 反转链表 * @param head * @return 反转后链表的头结点 */ private ListNode reverseList(ListNode head) { ListNode pre = null; ListNode next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }

返回链表左半区的最后一个节点（找中点）

/** * 返回链表左半区的最后一个节点 * @param head * @return 左半区的最后一个节点 */ private ListNode endOfFisrtHalf(ListNode head) { ListNode left = head; ListNode cur = head; while (cur.next != null && cur.next.next != null) { left = left.next; cur = cur.next.next; } return left; }

返回链表右半区的第一个节点（找中点）

/** * 返回链表右半区的第一个节点 * @param head * @return 右半区的第一个节点 */ private ListNode beginOfSecondHalf(ListNode head) { ListNode right = head.next; ListNode cur = head; while (cur.next != null && cur.next.next != null) { right = right.next; cur = cur.next.next; } return right; }

合并两个有序的单链表

/** * 合并两个有序的单链表 * @param l1 第一个链表的头结点 * @param l2 第二个链表的头结点 * @return */ public ListNode loopMethod(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); //开辟节点表示新的链表 ListNode pre = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { pre.next = l1; l1 = l1.next; } else { pre.next = l2; l2 = l2.next; } pre = pre.next; } //当有一放还有剩余元素时， //那剩下的值一定大于等于链表中已有的值，并且是有序的， //直接连接在链表尾部即可 pre.next = (l1 == null ? l2 : l1); return dummy.next; }

排序链表

/** * 利用归并排序链表 * @param head 链表的头结点 * @return */ public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } // 返回链表左半区的最后一个节点 ListNode mid = endOfFisrtHalf(head); ListNode rightHead = mid.next; mid.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); // 排序两个有序链表 return mergeTwoLists(left, right); }