Single list flip

leetcode206

recursive

    public ListNode reverseList(ListNode head) {
    
		if(head == null || head.next == null)
			return head;
		ListNode rever = reverseList(head.next);
		//1->2->3->4, here root=3,re=root.next=4,1->2->3,4->3
		head.next.next = head;
		head.next = null;
		return rever;
	}  

Non recursive

	public static Node Traversing(Node root) {
    
		if(root ==null)
			return null;
		Node preNode = null;
		Node curNode = root;
		Node nextNode =null;
		
		while(curNode!=null) {
    
			nextNode = curNode.next;
			curNode.next =preNode;
			preNode =curNode;
			curNode = nextNode;
		}
		return preNode;
	}

Two or two exchange nodes in a linked list

    public ListNode swapPairs(ListNode head) {
    
    	ListNode dummyHead = new ListNode(-1);
    	dummyHead.next = head;
    	ListNode q = dummyHead;
    	while(q.next != null && q.next.next != null) {
    
    		ListNode node1 = q.next;
        	ListNode node2 = node1.next;
        	ListNode nnext = node2.next;
            node2.next = node1;
            node1.next = nnext;
            q.next = node2;
            q = node1;
    	}
    	return dummyHead.next;
    }

K A set of flip list

class Solution {
    
    public ListNode reverseKGroup(ListNode head, int k) {
    
    	if(head == null)
    		return null;
    	ListNode dummyHead = new ListNode(-1);
    	dummyHead.next = head;
    	ListNode pre = dummyHead;
    	ListNode end = dummyHead;
    	while(end.next != null) {
    
    		for(int i = 0; i < k && end != null; i++) {
    
    			end = end.next;
    		}
    		if(end == null)
    			break;
    		// It is necessary to record the precursor and successor of the flipped linked list , It is convenient to connect the flipped part and the non flipped part after flipping 
    		// Two variables are required initially  pre  and  end,pre  Represents the precursor of the linked list to be flipped ,end  Represents the end of the linked list to be flipped 
    		// after k This cycle ,end  To the end , Record the successor of the linked list to be flipped  next = end.next
    		// Flip list , Then connect the three parts of the linked list , Then reset  pre  and  end  The pointer , Then go to the next cycle 
    		ListNode start = pre.next;
    		ListNode pnext = end.next;
    		end.next = null;//reverse:start~end,end Back broken 
    		pre.next = reverse(start);//pre：join The first part is the precursor and the overturned linked list 
    		start.next = pnext;//end~start:join  Flipped and not flipped 
    		pre = start;
    		end = pre;
    	}
    	return dummyHead.next;
        
    }
    private ListNode reverse(ListNode head) {
    
    	ListNode pre = null;
    	ListNode cur = head;
    	while(cur != null) {
    
    		ListNode pnext = cur.next;
    		cur.next = pre;
    		pre = cur;
    		cur = pnext;
    	}
    	return pre;//not return cur:cur =null this time.
    }

}