首页 > 其他 > 详细

Swap Two Nodes in Linked List

时间:2016-07-02 11:56:28      阅读:158      评论:0      收藏:0      [点我收藏+]

Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It‘s guaranteed there is no duplicate values in the linked list. If v1 or v2 does not exist in the given linked list, do nothing.

Notice

You should swap the two nodes with values v1 and v2. Do not directly swap the values of the two nodes.

Example

Given 1->2->3->4->null and v1 = 2, v2 = 4.

Return 1->4->3->2->null.

分析:

因为这题里涉及到四个nodes,node1, node1Parent, node2, node2Parent, 然后有了这四个nodes,我们就可以对它们进行换位,但是这里有一种特殊情况node1是node2的parent,或者node2是node1的parent,需要单独处理一下。

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     /**
11      * @param head a ListNode
12      * @oaram v1 an integer
13      * @param v2 an integer
14      * @return a new head of singly-linked list
15      */
16     public ListNode swapNodes(ListNode head, int v1, int v2) {
17         if (head == null) return null;
18         if (v1 == v2) return head;
19         
20         int dummyValue = Math.abs(v1) + Math.abs(v2) + 1;
21         
22         ListNode dummyHead = new ListNode(dummyValue);
23         dummyHead.next = head;
24         ListNode node1Parent = findNodeParent(dummyHead, v1);
25         ListNode node2Parent = findNodeParent(dummyHead, v2);
26         // if v1 or v2 doesn‘t exist, return
27         if (node1Parent == null || node2Parent == null) return head;
28         
29         ListNode node1 = node1Parent.next;
30         ListNode node2 = node2Parent.next;
31         // special case
32         if (node1.next == node2) {
33             node1Parent.next = node2;
34             node1.next = node2.next;
35             node2.next = node1;
36         } else if (node2.next == node1) {  // special case
37             node2Parent.next = node1;
38             node2.next = node1.next;
39             node1.next = node2;
40         } else {
41             ListNode temp = node2.next;
42             node2.next = node1.next;
43             node1.next = temp;
44             node1Parent.next = node2;
45             node2Parent.next = node1;
46         }
47         return dummyHead.next;
48     }
49     
50     private ListNode findNodeParent(ListNode head, int v1) {
51         while (head.next != null) {
52             if (head.next.val == v1) {
53                 return head;
54             } else {
55                 head = head.next;
56             }
57         }
58         return null;
59     }
60 }

转载请注明出处:cnblogs.com/beiyeqingteng/

Swap Two Nodes in Linked List

原文:http://www.cnblogs.com/beiyeqingteng/p/5634997.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!