给定一个单链表,请设定一个函数,将链表的奇数位节点和偶数位节点分别放在一起,重排后输出。
注意是节点的编号而非节点的数值。
数据范围:节点数量满足 ,节点中的值都满足
要求:空间复杂度 ,时间复杂度
{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内。
/* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ function oddEvenList( head ) { let arr=[]; for(let p=head;p;p=p.next) arr.push(p); let i=0,j=1,arr1=[],arr2=[]; while(arr[i]||arr[j]){ if(arr[i]) arr1.push(arr[i]); if(arr[j]) arr2.push(arr[j]); i+=2; j+=2; } arr=arr1.concat(arr2); for(let i=0;i<arr.length;i++){ if(i+1<arr.length) arr[i].next=arr[i+1]; else arr[i].next=null; } return arr[0]; } module.exports = { oddEvenList : oddEvenList };
哈哈哈哈,还有谁
function ListNode(x){ this.val = x; this.next = null; } if(!head)return null let cur = head ,index = 1 while(cur){ if(index%2 ==1){ cur.flag = true }else{ cur.flag = false } cur = cur.next index++ } let arr1 = [] ,arr2 = [] cur = head while(cur){ if(cur.flag){ arr1.push(cur.val) }else{ arr2.push(cur.val) } cur = cur.next } arr1.push(...arr2) let pHead = new ListNode(arr1[0]) cur = pHead for(let i=1;i<arr1.length;i++){ cur.next = new ListNode(arr1[i]) cur = cur.next } return pHead
function oddEvenList( head ) { // write code here if(!head) return head let odd = head ///扫描奇链节点 let even = head.next ///扫描偶链节点 let evenHead = even //保存偶数链的节点 while(even&&even.next){ odd.next = odd.next.next //指向下一个奇数节点 even.next = even.next.next //指向下一个奇数节点 odd = odd.next //odd推进到下一个奇数节点 even = even.next //even推进到下一个偶数节点 } odd.next = evenHead //奇数链连上偶数链 return head }