链表（篇3）链表中将所有的偶数移到奇数后面不改变原来的相对位置

本文主要是介绍链表（篇3）链表中将所有的偶数移到奇数后面不改变原来的相对位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个整数的链表，写一个函数来修改链表，使得所有偶数出现在修改链表的所有奇数之前。此外，保持偶数和奇数的顺序相同。

示例：
输入：17-> 15-> 8-> 12-> 10-> 5-> 4-> 1-> 7-> 6-> NULL
输出：8-> 12-> 10-> 4-> 6 - > 17-> 15-> 5-> 1-> 7-> NULL

输入：8-> 12-> 10-> 5-> 4-> 1-> 6-> NULL
输出：8-> 12-> 10-> 4-> 6-> 5-> 1-> NULL

//如果所有数字都是偶数，则不改变列表
输入：8-> 12-> 10-> NULL
输出：8-> 12-> 10-> NULL

//如果所有数字都是奇数，则不改变列表
输入：1-> 3-> 5-> 7-> NULL
输出：1-> 3-> 5-> 7-> NULL

解法1：
取下头结点，顺序取下后面的节点插到头节点后面，当该节点值是偶数时将其插入到最后面，如果是奇数将其插入到所有奇数后面偶数前面。依次遍历所有的节点。
时间复杂度O(N*N);
代码

ListNode Segregate(ListNode head){ListNode phead=new ListNode(0);ListNode pre=head;ListNode qre=phead;ListNode next;while(pre!=null){qre=phead;if((pre.val&1)==0){while(qre.next!= null){qre=qre.next;}next=pre;pre=pre.next;qre.next=next;next.next=null;//如果是偶数就直接放到新链表的最后面}else if((pre.val&1)==1){while(qre.next!=null&&(qre.next.val&1)==1){qre=qre.next;//如果是奇数，就放到新链表最后一个奇数的后面，第一个偶数的前面}if(qre.next== null){next=pre;pre=pre.next;qre.next=next;next.next=null;//如果新链表中没有偶数节点就将节点放在最后}else {next=pre.next;pre.next=qre.next;qre.next=pre;pre=next;//如果有偶数节点放在偶数节点前面。}}}return phead.next;}

解法2
先找到链表的最后一个节点，然后再遍历链表，将偶数节点依次连接到最后一个节点后面。要记住标记最后一个节点以便结束遍历。时间复杂度O(N)。

代码

ListNode Segregate(ListNode head,int tag){ListNode phead=new ListNode(0);ListNode tail;ListNode pre=head;phead.next=head;ListNode qre=phead;ListNode ptail;if(pre==null||pre.next==null)return head;while(pre.next!=null){pre=pre.next;}tail=pre;//找到最后一个节点pre=head;ptail=tail;while(pre!=tail.next){if((pre.val&1)==0){//当前节点值为偶数时将其放到链表的最后面qre.next=pre.next;ptail.next=pre;ptail=ptail.next;           }else {qre=qre.next;}pre=pre.next;}ptail.next=null;//最后尾指针一定要指向空，不然输出时循环不会结束。return phead.next;}