[数据结构与算法]Leetcode 143.重排链表(链表) 记录反思

思路:
取中点 + 反转后半段链表 + 合并前后链表

在做这一题的时候发现 Leetcode 206.反转链表 我还不会,所以先找了一篇文章学习了一下如何反转链表
(https://blog.csdn.net/qq_17550379/article/details/80647926)

取中点
快慢指针,快指针每次走两步,慢指针一部 ,当快指针走到尾部的时候,慢指针的位置就正好在中间

  private ListNode midNode(ListNode node){
        ListNode fast = node;
        ListNode show = node;
        while(fast.next != null && fast.next.next != null && show.next != null){
            fast = fast.next.next;
            show = show.next;
        }
        return show;
    }

反转链表
文章地址 : [反转链表] 我觉得我说的不清楚,大家可以看一下这篇文章

private ListNode reverseList(ListNode head){
       ListNode prev = null;
       ListNode cur = head;
       while(cur != null){
           ListNode temp = cur.next;
           cur.next = prev;
           prev = cur;
           cur = temp;
       }
       return prev;
    }

合并链表
循环一次的流程,思路不顺的同学可以稍微看一下

//lt1= l1.next;
	l1	lt1
	1 -> 2 -> 3 -> 4
	
//lt2= l2.next;
	l2	lt2
	8 -> 7 -> 6 -> 5
	
//l1.next = l2;
  	l1   l2
  	1 -> 8 -> 7 -> 6 -> 5
  	
//l1 = lt1;
  	l1
  	2 -> 3 -> 4
  	lt1
 
//l2.next = l1;
         l2   l1
    1 -> 8 -> 2 -> 3 -> 4
  
//l2 = lt2;
	l2
	7 -> 6 -> 5
	lt2

    private ListNode mergeList(ListNode l1,ListNode l2){
        ListNode lt1;
        ListNode lt2;
        while (l1 != null && l2 != null) {
            lt1= l1.next;
            lt2= l2.next;
            l1.next = l2;
            l1 = lt1;
            l2.next = l1;
            l2 = lt2;
        }
        return l1;
    }

总代码

class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = midNode(head);
        ListNode prev = reverseList(mid);
        mid.next = null;
        head = mergeList(head,prev);
    }
    private ListNode midNode(ListNode node){
        ListNode fast = node;
        ListNode show = node;
        while(fast.next != null && fast.next.next != null && show.next != null){
            fast = fast.next.next;
            show = show.next;
        }
        return show;
    }
    private ListNode reverseList(ListNode head){
       ListNode prev = null;
       ListNode cur = head;
       while(cur != null){
           ListNode temp = cur.next;
           cur.next = prev;
           prev = cur;
           cur = temp;
       }
       return prev;
    }
    private ListNode mergeList(ListNode l1,ListNode l2){
        ListNode l1_temp;
        ListNode l2_temp;
        while (l1 != null && l2 != null) {
            l1_temp = l1.next;
            l2_temp = l2.next;
            l1.next = l2;
            l1 = l1_temp;
            l2.next = l1;
            l2 = l2_temp;
        }
        return l1;
    }
}