首页 > 代码库 > 24. Swap Nodes in Pairs
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
经典解法:设一个哨兵然后前两个互换之后到后两个。
public ListNode SwapPairs(ListNode head) { if (head == null) return head; var sentinel = new ListNode(-1); sentinel.next = head; var dummy = sentinel; while (head != null && head.next != null) { dummy.next = head.next; head.next = head.next.next; dummy.next.next = head; dummy = head; head = head.next; } return sentinel.next; /*ListNode sentiential = new ListNode(0); sentiential.next = head; ListNode p = head; ListNode d = sentiential; while (p != null && p.next != null) { d.next = p.next; d = p; p = p.next.next; d.next.next = d; } d.next = p; return sentiential.next;*/ }
这个地方我一开始犯了一个错误是,即把注释掉的那行放在了下面.
public ListNode SwapPairs(ListNode head) { if(head == null || head.next == null) return head; var sentinel = new ListNode(-1); sentinel.next = head; var dummy = sentinel; while(head != null && head.next != null) { sentinel.next = head.next; //head.next = head.next.next; sentinel.next.next = head; sentinel = head; head.next = head.next.next; head = head.next; } return dummy.next; }
这个会使出现问题，head 为1。
sentinel.next = head.next;
=> sentinel.next 为2
sentinel.next.next = head;
=> 2.next = head = 1;
此时1.next依然为2. 则1.next 为2，2.next 为1，deadlock.需要先将head.next 重新赋值.
或者将list 间隔split成两个list，然后再逐个拼起来。
public ListNode SwapPairs(ListNode head) { if(head == null || head.next == null) return head; var sec = head.next; var sentinel = new ListNode(-1); var dummy = sentinel; var headSentinel = head; ListNode nextNode = null; ListNode nextSNode =null; while(head != null && head.next != null) { sentinel.next = head.next; head.next = head.next.next; sentinel = sentinel.next; head = head.next; } var front = dummy.next; var second = headSentinel; while(front != null) { nextNode = front.next; nextSNode = second.next; front.next = second; second.next = nextNode; front = nextNode; second = nextSNode; } return dummy.next; }
24. Swap Nodes in Pairs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。