2022-1-2 1721. 交换链表中的节点 143. 重排链表

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int n=0;
        ListNode c=head;
        while(c!=null){
            n++;
            c=c.next;
        }
        //卡住的原因：特殊情况没有考虑全面
        //1.链表只有一个节点时
        //2.正数第k个节点和倒数第k个节点是同一个节点时
        if(n==1 || (n-k)==(k-1)) return head;
        //倒数第k个节点 n-k
        int temp1=0;
        int max1=Math.max(n-k,k-1);
        int min1=Math.min(n-k,k-1);
        ListNode cur=head;
        ListNode temp=null;
        for(int i=0;i 
143. 重排链表 
class Solution {
    public void reorderList(ListNode head) {
        //自己做时特殊情况忘记了考虑
        if(head==null || head.next==null ||head.next.next==null) return;
      
        //找中点时采用快慢指针的办法
        //找中点，链表分成两个
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode newHead = slow.next;
    slow.next = null;


        ListNode new1=reverse(newHead);
        ListNode x=head;
        //采用头插法重组链表
        while(new1 != null){
            ListNode te=new1.next;
           new1.next=x.next;
           x.next=new1;
            x=new1.next;
           new1=te;
        }
        
    }
   public ListNode reverse(ListNode head) {
        ListNode temp = null;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5692280.html