给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。
注意是节点的编号而非节点的数值。
数据范围:节点数量满足 ,节点中的值都满足
要求:空间复杂度 ,时间复杂度
{1,2,3,4,5,6}
{1,3,5,2,4,6}
1->2->3->4->5->6->NULL重排后为1->3->5->2->4->6->NULL
{1,4,6,3,7}
{1,6,7,4,3}
1->4->6->3->7->NULL重排后为1->6->7->4->3->NULL
奇数位节点有1,6,7,偶数位节点有4,3。重排后为1,6,7,4,3
链表长度不大于200000。每个数范围均在int内。
public ListNode oddEvenList (ListNode head) { // write code here ListNode p1=new ListNode(0) ,p3=p1; ListNode p2=new ListNode(0) ,p4=p2; boolean flag=true; while(head!=null){ if(flag){ p3.next=head; p3=p3.next; }else{ p4.next=head; p4=p4.next; } head=head.next; flag=!flag; } p3.next=p2.next; p4.next=null; return p1.next; }
public ListNode oddEvenList (ListNode head) { // write code here if (head == null) { return null; } int cnt = 1; ListNode dummyj = new ListNode(0); ListNode dummyo = new ListNode(0); ListNode p1 = dummyj, p2 = dummyo, p = head; while (p != null) { if (cnt % 2 != 0) { p1.next = p; p1 = p1.next; } else { p2.next = p; p2 = p2.next; } p = p.next; cnt += 1; } p1.next = dummyo.next; p2.next = null; return dummyj.next; }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { if (head==null||head.next==null||head.next.next==null){ return head; } ListNode odd = new ListNode(head.val), even = new ListNode(head.next.val); ListNode left = odd, right = even, oddNext = null, evenNext = null; int index = 2; head = head.next.next; //3 while (head != null) { index++; if (index % 2 == 1) { oddNext = new ListNode(head.val); odd.next = oddNext; odd = odd.next; } else { evenNext = new ListNode(head.val); even.next = evenNext; even = even.next; if (head.next == null) { even.next = null; } } head = head.next; } odd.next = right; return left; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { // write code here ListNode even=new ListNode(-1); ListNode e=even; ListNode odd=new ListNode(-1); ListNode o=odd; int count=0; ListNode p=head; while(p!=null){ count++; if(count%2==0){ ListNode tmp=p.next; o.next=p; p.next=null; o=p; p=tmp; }else{ ListNode tmp=p.next; e.next=p; p.next=null; e=p; p=tmp; } } e.next=odd.next; return even.next; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { // write code here // 注意没有元素、只有1个元素、只有两个元素的情况 if (head == null || head.next == null || head.next.next == null) { return head; } ListNode l1 = head; ListNode l1h = head; ListNode l2 = head.next; ListNode l2h = head.next; while (true) { l1.next = l2.next; l1 = l1.next; if (l1.next == null) break; l2.next = l1.next; l2 = l2.next; if (l2.next == null) break; } l1.next = l2h; // 注意l2的next要设为null,避免循环出现 l2.next = null; ListNode l1h1 = l1h; return l1h; } }
public ListNode oddEvenList (ListNode head) { // write code here ListNode result = null; if(head==null||head.next==null){ return head; } ListNode oddlist = head, evenlist = head.next, temp = head.next.next; result=oddlist; ListNode evenhead=evenlist; while(temp!=null&&temp.next!=null){ oddlist.next=temp; oddlist=oddlist.next; temp=temp.next; evenlist.next=temp; evenlist=evenlist.next; temp=temp.next; } if(temp!=null){ oddlist.next=temp; oddlist=oddlist.next; evenlist.next=null; } oddlist.next=evenhead; return result; }
public ListNode oddEvenList (ListNode head) { ListNode dummy=new ListNode(-1); dummy.next=head; if(head==null) return null; ListNode odd=head; ListNode evenHead=head.next; ListNode even=evenHead; while(even!=null&&even.next!=null){ odd.next=even.next; odd=odd.next; even.next=odd.next; even=even.next; } odd.next=evenHead; return dummy.next; }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { // write code here //判断 head == null if (head == null) { return null; } int count = 0; ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = head; while (cur != null) { count++; if (count % 2 != 0) { if (bs == null) { bs = cur; be = cur; } else { be.next = cur; be = be.next; } } else { if (as == null) { as = cur; ae = cur; } else { ae.next = cur; ae = ae.next; } } cur = cur.next; } be.next = as; if(as != null) { ae.next = null; } return bs; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { // write code here ArrayList<Integer> list1 = new ArrayList<>(); ArrayList<Integer> list2 = new ArrayList<>(); ArrayList<Integer> list3 = new ArrayList<>(); while (head != null) { list1.add(head.val); if(head.next!=null){ head = head.next; list2.add(head.val); } head = head.next; } list3.addAll(list1); list3.addAll(list2); ListNode sen = new ListNode(-1); ListNode cur = sen; for (int i = 0; i < list3.size(); i++) { cur.next = new ListNode(list3.get(i)); cur = cur.next; } return sen.next; } }
import java.util.*; public class Solution { public ListNode oddEvenList (ListNode head) { if (head == null) { return null; } //phead1 phead2 分别存储奇数位结点和偶数位结点 //p1 p2分别遍历两个链表,最后第一个链表的最后连接第二个链表的开始 ListNode phead1 = new ListNode(-1); ListNode p1 = phead1; ListNode phead2 = new ListNode(-1); ListNode p2 = phead2; ListNode cur = head; int idx = 1; ListNode tmp; while (cur != null) { tmp = cur; cur = cur.next; tmp.next = null; if (idx % 2 == 1) { p1.next = tmp; p1 = p1.next; } else { p2.next = tmp; p2 = p2.next; } idx++; } p1.next = phead2.next; return phead1.next; } }
public ListNode oddEvenList (ListNode head) { //空 一个 两个节点 直接返回 if(head==null||head.next==null||head.next.next==null) return head; ListNode snd = head.next;//偶数头 ListNode cur1 = head;//处理奇数节点 ListNode cur2 = snd;//处理偶数节点 while(cur1!=null&&cur2!=null){//奇数连接、偶数连接 cur1.next = cur2.next; if(cur2.next==null) break; cur1 = cur2.next; cur2.next = cur1.next; cur2 = cur1.next; } cur1.next = snd;//奇数尾连接偶数头 return head; }
public class Solution { public ListNode oddEvenList (ListNode head) { if (head == null || head.next == null || head.next.next == null) { return head; } ListNode start1 = head; ListNode start2 = head.next; ListNode temp1 = start1; ListNode temp2 = start2; while(start2 != null && start2.next != null){ start1.next = start1.next.next; start2.next = start2.next.next; start1 = start1.next; start2 = start2.next; } start1.next = temp2; return temp1; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { //判断head为null与只有一个节点时候,返回head if(head==null){ return null; } ListNode odd = head; ListNode even = head.next; ListNode tempodd = odd; ListNode tempeven = even; //对链表进行循环 //当有奇数个节点时候,tempeven.next==null为结束 //当有偶数个节点时候,tempodd.next==null为结束 while(tempodd.next!=null && tempeven.next!=null){ tempodd.next = tempeven.next; tempodd = tempodd.next; tempeven.next = tempodd.next; tempeven = tempeven.next; } //最后让2个链表进行连接 tempodd.next = even; return odd; } }
public ListNode oddEvenList (ListNode head) { // write code here if(head == null || head.next == null || head.next.next == null){ return head; } ListNode oddTail = head; ListNode evenHead = head.next; ListNode evenTail = head.next; while(oddTail.next != null && evenTail.next != null){ oddTail.next = evenTail.next; oddTail = oddTail.next; evenTail.next = oddTail.next; evenTail = evenTail.next; } oddTail.next = evenHead; return head; }