本文目录
- 如何链表反转
- java:已知单链表H,利用栈的原理写一个算法将其倒置
- 问个java链表逆转的问题
- 单链表就地逆置有几种方法
- 借助栈实现单链表上的逆置运算
- 设有一个表头指针的单链表，试设计一个算法，通过历遍一趟链表，将链表的所有的接点的链接的方向逆转
- 用java来编写一个单链表类的成员函数，实现对头结点的单链表就地逆置的操作
- 已知单链表H，利用栈的原理写一个算法将其倒置
- java linked list里的元素顺序反过来
- 请用C或者Java语言写出实现将单向链表顺序反转的函数
如何链表反转
链表反转单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1-》2-》3-》4-》5 通过反转后成为5-》4-》3-》2-》1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：struct linka { int data; linka* next;};void reverse(linka*& head){ if(head ==NULL) return; linka*pre, *cur, *ne; pre=head; cur=head-》next; while(cur) { ne = cur-》next; cur-》next = pre; pre = cur; cur = ne; } head-》next = NULL; head = pre;}还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：linka* reverse(linka* p,linka*& head){ if(p == NULL || p-》next == NULL) { head=p; return p; } else { linka* tmp = reverse(p-》next,head); tmp-》next = p; return p; }}
java:已知单链表H,利用栈的原理写一个算法将其倒置
import myjava.Node;import myjava.SinglyLinkedList;import myjava.SeqStack;public class ReverseLinkedList《E》 extends SinglyLinkedList《E》 {public ReverseLinkedList(){super();} public void reverse(ReverseLinkedList《E》 list){ SeqStack《E》 stack = new SeqStack《E》(); Node《E》 p = this.head ; while(p != null){ stack.push(p.data); p = p.next; } list.clear(); while(!stack.isEmpty()){ list.add(stack.pop()); } } public static void main (String args) { ReverseLinkedList《Integer》 list = new ReverseLinkedList《Integer》(); for(int i = 1;i 《 6;i++){ list.add(0,new Integer(i)); } System.out.println("单列表 "+list.toString()); list.reverse(list); System.out.println("逆转后 "+list.toString());}}
问个java链表逆转的问题
在java中对象的赋值都是传递引用你在在Insert方法中并没有创建一个新节点，只是引用之前的节点所以你在往第二个表中插入元素后，两个表的节点变量其实指向了一个对象因此在Insert方法中要真正的创建一个新节点void Insert(LinkedNode ln){LinkedNode tmp = new LinkedNode(ln.value);if(Head==null){ //如果头结点为空,那么附值给头结点Head = tmp;Last = Head; //Last(最后一个结点)指向Head,因为此时只有一个结点,所以即是头结点,也是最后一个结点} else {Last.next = tmp; //将要插入的结点附给Last.nextLast.next.previous = Last; //新插入的结点的前一结点指向LastLast = Last.next; //更新Last为最后一个}}
单链表就地逆置有几种方法
单链表就地逆置的两种(递归与普通循环) 1.用递归算法,对于不带头结点的单链表（a1,a2,a3,a4,a5,a6）逆置后的结果为（a6,a5,a4,a3,a2,a1）考虑递归算法，若只有一个结点，则直接返回，若存在两个结点（a1,a2）则需要做的操作有： a2-》next=a1;a1-》next=NULL;return a2;a2即新的头结点，若有三个结点,则应先将子链（a2,a3）先逆置且返回该子链的新的头结点，然后把子链（a2,a3）当作一个复合结点a2’,组成新的二元组（a1,a2’）然后就可以执行前面相同的操作：a2’-》next=a1;a1-》next=NULL;return a3’;即可，多个以上的结点可同理得到，Node *Reverse(Node *head){ Node *p=head; if(p==NULL) return NULL; //若是空链表，返回空 Node *q=p-》next; if(q==NULL) return p; //若只有一个结点，直接返回 else head=Reverse(q); //记录子序列的新的头结点 q-》next=p; //当前结点与已经逆置的子序列看成是前后的两个结点p,q，作相应的逆置操作 p-》next=NULL; return head; //返回新的子序列的头结点}2.用普通算法循环逆置（头插法重新建立带头结点的新链表）Node *Reverse(Node *head){ Node *p=head-》next; if(p)//若链表不为空，则逆置，否则，空操作 { Node *q=p-》next; head-》next=NULL;//头结点分离 while(p) { p-》next=head-》next; //头插法建立链表 head-》next=p; if(q) //操作空指针的时候一定要非常注意，很容易出错 { p=q; q=p-》next; } else break; } } return head;}
借助栈实现单链表上的逆置运算
栈先入后出，链表从投开始遍历；所以如栈然后再依次出栈就完成了逆置；现写的，没有测试，不过应该没问题：#define int ElemTypetypedef struct Node{ ElemType data; Node *next;}Node, *List;List reverseList(List head){ assert(head); if (head-》next == NULL) //如果链表长度为1，就不需要利用栈了 return head; stack《List》 listS; //从头开始入栈 while (head != NULL) { listS.push(head); head = head-》next; } //出栈 List pHead = listS.top(); //保存头节点 List pre = NULL , cur = NULL; //当前节点和前一个节点 while(listS.size()) { //如果是第一个节点 if (pre == NULL){ pre = listS.top(); listS.pop(); } //不是第一个节点 else{ cur = listS.top(); pre-》next = cur; pre = cur; listS.top(); } } pre -》next = NULL; //置尾结点的下一个节点为NULL； return pHead; }
设有一个表头指针的单链表，试设计一个算法，通过历遍一趟链表，将链表的所有的接点的链接的方向逆转
//对链表实现转置的函数template《class T》void List《T》:: reverse(){//转置函数的实现LinkNode《T》*h=first,*p,*q; p=h-》link; h-》link=NULL;while(p!=NULL){q=p; //把q指向头结点p=p-》link;//让p指向他的下一个结点q-》link=h-》link;//把h-》link这个空结点连接为q的下一个结点h-》link=q; //把 q的位置用h-》link来代替}//感觉你这程序是不是有错误
用java来编写一个单链表类的成员函数，实现对头结点的单链表就地逆置的操作
逆置有两种方法，第一是把所有节点反过来。还有一种就是改变节点中的值。第一种情况，其实可以考虑用头插法，来实现逆置。下面的算法是基于头插法的思想，逆置链表的，仅供参考。LinkList anti_linklist(LinkList demo){LInkList *p,*q;//work pointerLinkList head;head=new LinkList();head-》next=null;//init head pointerp=demo-》head-》next;//make p points to the first nodeif(p==null) return null;//the linklist is nullwhile(p!=null){q=p;q-》next=head-》next;head-》next=q;p=p-》next;}}
已知单链表H，利用栈的原理写一个算法将其倒置
1.建立一个单链表2.建立一个栈3.利用头指针顺序遍历单链表中的所有节点，每访问一个节点，进行一次入栈操作，把当前节点值压入栈中。4.对栈中所有元素进行出栈操作，把从栈中弹出的元素依次存放在单链表中从第一个节点开始的所有节点中。
java linked list里的元素顺序反过来
定义一个LinkedList《Integer》 templist = new LinkedList《》();来存储list里面的值，通过迭代list，将值插入在templist的头上，那么templist就是list的反转了，最后将templist赋值给list就行了！
如下代码：
public void reverse() {LinkedList《Integer》 list = new LinkedList《》();LinkedList《Integer》 templist = new LinkedList《》();int i = 0;while (i 《 6) {list.add(i);i++;}Iterator《Integer》 it = list.iterator();int m;while (it.hasNext() && i 》= 0) {m = it.next();templist.addFirst(m);i--;}list = templist;System.out.println(list);}
运行结果为：
5 4 3 2 1 0
从API中可以看到List等Collection的实现并没有同步化，如果在多线程应用程序中出现同时访问，而且出现修改操作的时候都要求外部操作同步化；调用Iterator操作获得的Iterator对象在多线程修改Set的时候也自动失效，并抛出java.util.ConcurrentModificationException。这种实现机制是fail-fast，对外部的修改并不能提供任何保证。
Iterator是工作在一个独立的线程中，并且拥有一个 mutex锁，就是说Iterator在工作的时候，是不允许被迭代的对象被改变的。
Iterator被创建的时候，建立了一个内存索引表（单链表），这个索引表指向原来的对象，当原来的对象数量改变的时候，这个索引表的内容没有同步改变，所以当索引指针往下移动的时候，便找不到要迭代的对象，于是产生错误。
List、Set等是动态的，可变对象数量的数据结构，但是Iterator则是单向不可变，只能顺序读取，不能逆序操作的数据结构，当 Iterator指向的原始数据发生变化时，Iterator自己就迷失了方向。
所以如果像下面这么写就会抛出异常java.util.ConcurrentModificationException
：
public void reverse() {LinkedList《Integer》 list = new LinkedList《》();int i = 0;while (i 《 6) {list.add(i);i++;}Iterator《Integer》 it = list.iterator();int m;while (it.hasNext() && i 》= 0) {m = it.next();list.add(m);list.remove(0);i--;}System.out.println(list);}
请用C或者Java语言写出实现将单向链表顺序反转的函数
ListItem* reverseList(ListItem *pHead){ListItem *p1,*p2;p1=pHead;p2=0;while(p1!=0){pHead=p1;p1=p1-》next;pHead-》next=p2;p2=pHead;}return pHead;}
