leetcode24:两两交换相邻的节点
描述:
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
说明:
你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值,而且对于链表的操作,一般都要求操作节点而仅仅是修改节点上的数据。
思路:
因为需要操作头结点(head),为了统一过程,需要新建一个表头节点(preHead)。具体的操作过程,我将使用图片来说明。
首先整个操作需要使用三个指针来完成。
这里需要说一下,之前在思考的时候,节点上的指针应该是跟着节点的位置的变化而变化的,之前总把节点假想成下标(虽然这样做没有错,但是在有些情况下可能会操作思维上的漏洞),希望以此为警戒。
这一步就是移动指针的位置了
重复之前的动作
到了这里就要思考:程序什么时候终止?首先left每次移动之后,都是移动到上一步交换后的第二个元素上,所以left不会首先为null。思考mid指针,如果节点的个数为偶数,那么最后以此交换完成后,mid移动的位置就为null(程序结束);如果节点的个数为奇数,那么就如下图所示,此时没有相邻的节点和他交换(所以此时程序也应该终止)。
好了,知道了代码的逻辑过程和终止条件,就剩下写写代码了
public ListNode swapPairs(ListNode head) {
if(head==null)
return null;
//表头节点,默认链表中的数据都为正数
ListNode preHead = new ListNode(-1);
preHead.next=head;
ListNode left=preHead;
ListNode mid=head;
if(head.next==null) //如果只有一个节点,直接返回这个节点
return head;
ListNode right=head.next;
while(mid!=null && mid.next!=null){
mid.next=right.next; //交换节点的过程
right.next=mid;
left.next=right;
left=mid; //移动节点的过程
mid=left.next;
if(mid!=null) //注意细节:首先要保证mid不为null,才能将mid.next赋值给right。
right=mid.next;
}
return preHead.next;
}
收获:
这道题的要点,我感觉是在交换节点的过程中各节点指针域的变化过程,然后就是表头节点的使用(一般如果是删除节点操作或者有可能操作头节点的操作都需要使用表头节点)。
感想:
有的时候只有被打痛了,才知道疼。在经历的面试时对算法的茫然和无助,才知道这个重要性。编程是一点一步积累出来的,希望自己一直坚持下去,与君共勉。
上一篇: js中交换两个变量的方式
下一篇: 面试题50_树中两个节点的最低公共祖先