LinkedList 链表总结 - Ryan的修炼之路

leetcode好久不刷了, 今天按照类型来刷linkedlist一类的, 总结一下.

反转链表

打算从今天起反转链表都统一方式来做, 这样便于记忆. 方法就是设立一个pre前驱节点, 然后有pre的下一个为p1, 再下一个为p2, 以及结尾节点tail.把p2不停的往pre后面插直到p2=tail为止, 这样就完成了链表的反转

部分反转

public void reverse(ListNode pre, ListNode last) {        ListNode cur = pre.next;        ListNode next = cur.next;        while (next != last) {cur.next = next.next;next.next = pre.next;pre.next = next;next = cur.next;        }    }

全反转

对于反转全部链表 pre就是dummy节点或者null, tail也是null

public ListNode reverse(ListNode head) {        if (head == null || head.next == null) {return head;        }        ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode prev = dummy;;        ListNode p1 = head;        ListNode p2 = head.next;        while(p2 != null){p1.next = p2.next;p2.next = prev.next;prev.next = p2;p2 = p1.next;        }        return dummy.next;    }

找中点

while (fast.next != null && fast.next.next != null) {    fast = fast.next.next;    slow = slow.next;}

slow之后的就为链表后半部分