我想知道是否存在一些逻辑来仅使用两个指针来反转链表.
以下用于使用三个指针(即p,q,r)反转单个链表:
struct node {
int data;
struct node *link;
};
void reverse() {
struct node *p = first,
*q = NULL,
*r;
while (p != NULL) {
r = q;
q = p;
p = p->link;
q->link = r;
}
first = q;
}
还有其他替代方法来反转链表吗？在时间复杂度方面,逆转单链表的最佳逻辑是什么？
这是在面试的书面测试期间提出的编程问题."你有两个已经排序的单链表,你必须合并它们并返回新列表的头部而不创建任何新的额外节点.返回的列表也应该排序"
方法签名是:Node MergeLists(Node list1,Node list2);
节点类如下:
class Node{
int data;
Node next;
}
我尝试了很多解决方案,但没有创建一个额外的节点螺丝.请帮忙.
以下是随附的博客文章http://techieme.in/merging-two-sorted-singly-linked-list/
我正在编写一些基本遵循以下格式的代码:
public static boolean isIncluded(E element) {
Node<E> c = head;
while (c != null) {
if (cursor.getElement().equals(element)) {
return true;
}
c = c.getNext();
}
return false;
}
代码将搜索节点列表中的元素.但是,我的问题是,如果while循环确实找到了if语句说它应该返回true的元素,它是否会返回true并打破循环？此外,如果它确实然后中断循环,它将继续通过该方法并仍然返回false,或者一旦返回值,方法是否完成？
谢谢
有人能告诉我为什么我的代码有效吗？我想在java中反转单个链表:这是方法(不能正常工作)
public void reverseList(){
Node before = null;
Node tmp = head;
Node next = tmp.next;
while(tmp != null){
if(next == null)
return;
tmp.next = before;
before = tmp;
tmp = next;
next = next.next;
}
}
这是Node类:
public class Node{
public int data;
public Node next;
public Node(int data, Node next){
this.data = data;
this.next = next;
}
}
在输入4-> 3-> 2-> 1我得到输出4.我调试它并正确设置指针,但我仍然不明白为什么它只输出4.
我试图扭转链表.这是我提出的代码:
public static void Reverse(ref Node root)
{
Node tmp = root;
Node nroot = null;
Node prev = null;
while (tmp != null)
{
//Make a new node and copy tmp
nroot = new Node();
nroot.data = tmp.data;
nroot.next = prev;
prev = nroot;
tmp = tmp.next;
}
root = nroot;
}
它运作良好.想知道是否有可能避免创建新节点.想对此有所建议.
是否有任何方法可以使用不超过两个指针找到链接列表中的循环开始？ 我不想访问每个节点并标记它并报告第一个节点已经被看到.有没有其他方法可以做到这一点？
我正在阅读的书,链接列表数据结构简介(演示文稿21),有2个链表的例子.这是第一个:
EnemySpaceShip* getNewEnemy ()
{
EnemySpaceShip* p_ship = new EnemySpaceShip;
p_ship->x_coordinate = 0;
p_ship->y_coordinate = 0;
p_ship->weapon_power = 20;
p_ship->p_next_enemy = p_enemies;
p_enemies = p_ship;
return p_ship;
}
链接列表的第二个示例是这样的:
EnemySpaceShip* addNewEnemyToList (EnemySpaceShip* p_list)
{
EnemySpaceShip* p_ship = new EnemySpaceShip;
p_ship->x_coordinate = 0;
p_ship->y_coordinate = 0;
p_ship->weapon_power = 20;
p_ship->p_next_enemy = p_list;
return p_ship;
}
然后这本书写道:
请注意,此函数不同,
getNewEnemy因为它返回指向列表的指针,而不是新的敌人.
我不明白的是他的意思是"第二个函数返回一个指向列表的指针"和"第一个函数返回新的敌人".我以为他们都创造了一个叫做的新敌人p_ship(既是指针又是新敌人)并将其归还.这句话是什么意思？
我不清楚理解为什么在单个链表的末尾删除在O(1)时间内,正如维基百科的文章所说.
单个链表由节点组成.节点包含某种数据,以及对下一个节点的引用.链表中最后一个节点的引用为null.
-------------- -------------- --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
-------------- -------------- --------------
我确实可以删除O(1)中的最后一个节点.但是在这种情况下,您不会将新最后一个节点(前一个节点)的引用设置为null,因为它仍包含对已删除的最后一个节点的引用.所以我想知道他们在运行时分析中是否忽略了这一点？或者它是否被认为你不必改变它,因为引用,好吧,只是指向什么,并且这被视为null？
因为如果它不会被忽略,我会认为删除是O(n).因为您必须遍历整个列表才能到达新的最后一个节点并将其引用也设置为null.只有在双链表中,它才真正是O(1).
-edit-也许这种观点会让人更加清晰.但我看到"删除节点"成功删除节点本身并将先前的引用设置为null.
Node reverse(Node head) {
Node previous = null;
Node current = head;
Node forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
究竟是如何扭转名单的呢？我知道它首先将第二个节点设置为forward.然后它说current.next等于一个null节点previous.然后它说previous现在current.最后current成为forward？
我似乎无法掌握这一点以及它的逆转方式.有人可以解释这是如何工作的吗？
java algorithm linked-list data-structures singly-linked-list
当head作为参数发送给它时,以下代码可以正常工作.由于我是C的新手,我无法理解它是如何工作的.请帮帮我.
struct node *recursiveReverseLL(struct node *list)
{
struct node *revHead;
if (list == NULL || list->link == NULL)
{
return list;
}
revHead = recursiveReverseLL(list->link);
list->link->link = list;
list->link = NULL;
return revHead;
}
我不知道如何使用这些递归调用提供链接.即)如果链接为,
1 -> 2 -> 3 -> 4
然后hw被改变为,
4 -> 3 -> 2 -> 1