2019独角兽企业重金招聘Python工程师标准>>> 
原题
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.
题目大意
给定一个单链表成对交换两个相邻的结点。算法法应该做常量辅助空间不能改结点的值只能交换结点。
解题思路
使用一个头结点root来辅助操作对要进行交换的链表每两个的位置进行交换并且把交换后的结点接到root的链表上直到所有的结点都处理完。
代码实现
结点类
public class ListNode {int val;ListNode next;ListNode(int x) {val x;next null;}}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
算法实现类
public class Solution {public ListNode swapPairs(ListNode head) {ListNode node new ListNode(0); // 头结点node.next head;// p指向新的链表的尾结点ListNode p node;ListNode tmp;// 每两个进行操作while (p.next ! null null) {// 记录下一次要进行处理的位置tmp p.next.next;// 下面三句完成两个结点交换p.next.next tmp.next;tmp.next p.next;p.next tmp;// 指向返回链表的新的尾结点p tmp.next;}head node.next;node.next null;return head;}}
背景 交换一个链表中连续的两个节点的位置。比如1->2->3->4 返回2->1->4->3.
[java] view plain copy
print?
[java] view plain copy
print?
首先我们需要一个多余的节点来存储要交换的两个节点的第一个节点上一级 然后对着两个节点进行交换 再完成两个节点的交换之后 我们需要将之前存储的第一个节点的上一级进行赋值使其指向交换后的第一个节点这个过程很重要如果缺失了这一过程那么我们将丢失链接。 然后就这个多余节点赋值为交换之后的第二个节点也就是为下一次的交换做准备
转:https://my.oschina.net/u/2822116/blog/805151