两两反转单项链表就是把每两个数反转一次。如下:
A -> B -> C ->D -> E -> F ->G -> H -> I 两两反转后变为B -> A -> D ->C -> F -> E ->H -> G -> I
分析:
我们需要两个“指针”指着当前要反转的两个值。两两反转后,我们还需要记录下一个的值,换句话说,我们反转 A 和 B 后, 需要记录 C 值,我们才能够不断向下走,直到到达链表末端,所以,我们还需要另一个指向下一个值的“指针”。
反转以后,A的下一个是C, 但是,实际上,A的下一个应该是D,所以,每次反转时,我们需要更新前一个值的下一个值,也就是说把 A -> C 改成 A -> D。
所以,要完成这个操作,我们总共需要4个“指针”。
代码:
class Node {
char value;
Node next;
}
public static Node reverseInPair(Node current) {
if (current == null || current.next == null) return current;
Node head = current.next;//save the head of the list
Node previousNode = null;
while(current != null && current.next != null) {
//get the current node's next and "nextnext" node
Node nextNode = current.next;
Node nextNextNode = nextNode.next;
//exchange the "next" node
nextNode.next = current;
current.next = nextNextNode;
//update the "next" value of the previous node
if (previousNode != null) {
previousNode.next = nextNode;
}
previousNode = current;
current = nextNextNode;
}
return head;
}
转载请注明出处:
http://blog.csdn.net/beiyeqingteng/
分享到:
相关推荐
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
各种数据结构、算法及实用的C#源代码.C#,单向链表(Simply Linked List)快速排序(Quick Sort)算法与源代码.单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部...
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
单向循环链表(Singly Circular Linked List)是一种特殊的链表,它与普通的单向链表非常相似,唯一的区别在于尾节点的next指针指向头节点而不是空。这样就形成了一个循环,使得链表中的节点可以通过循环遍历而不会...
题目描述分别实现反转单向链表和反转双向链表的函数。【要求】 如果链表长度为N, 时间复杂度要求为O(N), 额外空间复杂度要求为O(1)解题思路反转单向链表反转
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)。 4.在单向链表中删除所有的偶数元素结点。 5.编写在非递减...
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
将一个单向链表反向连接
本文件描述单向链表类模板。移植时,仅需要本文件
C#,单向链表(Simply Linked List)的插入排序(Insertion Sort)算法与源代码 所谓插入排序法乃是将一个数目插入该占据的位置。 假设我们输入的是 “5,1,4,2,3” 我们从第二个数字开始,这个数字是1,我们的...
培训班老师自己写的单向链表,代码非常全,也很好理解,可执行。
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
C 语言版 单向链表 #include #include typedef struct student { int num; struct student *next; }st; st *creat() //创建链表 { st *head , *tail , *p; int num = 0; head = tail = p = NULL; printf...
单向链表的反转是一个经常被问到的一个面试题,也是一个非常基础的问题。比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->1。 最容易想到的方法遍历一遍链表,利用一个辅助指针,存储遍历过程中...
这是在面试中很常见的一个例子,实现单向链表的逆转,这个例子是用递归法实现的,一个简单的单向链表的例子