微信

使用微信服务,更方便

职友集>程序员面试题 > 单链表交换任意两个元素(不包括表头)

单链表交换任意两个元素(不包括表头)

2015-06-30 06:30:01 阅读( 99 )

601人 收藏本页

标签:程序员面试题

先一次遍历找到这两个元素curr1和curr2,同时存储这两个元素的前驱元素pre1和pre2。
然后大换血
public static Link SwitchPoints(Link head, Link p, Link q)
{
if (p == head || q == head)
throw new Exception(“No exchange with head”);
if (p == q)
return head;
//find p and q in the link
Link curr = head;
Link curr1 = p;
Link curr2 = q;
Link pre1 = null;
Link pre2 = null;

int count = 0;
while (curr != null)
{
if (curr.Next == p)
{
pre1 = curr;
count++;
if (count == 2)
break;
}
else if (curr.Next == q)
{
pre2 = curr;
count++;
if (count == 2)
break;
}
curr = curr.Next;
}
curr = curr1.Next;
pre1.Next = curr2;
curr1.Next = curr2.Next;
pre2.Next = curr1;
curr2.Next = curr;
return head;
}
注意特例,如果相同元素,就没有必要交换;如果有一个是表头,就不交换。

来自分智网

下一篇:两个单链表相交,计算相交点

上一篇:判断两个单链表是否相交

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题