如何使用仅两个指针反转单向链表？

Question

如何使用仅两个指针反转单向链表？

calgorithmdata-structureslinked-listsingly-linked-list

114

我想知道是否存在一种逻辑可以仅使用两个指针来反转单链表。

以下方法使用三个指针，分别为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;
}

有没有其他替代方法来反转链表？在时间复杂度方面，反转单向链表的最佳逻辑是什么？

- Madhan

1

可能重复：https://dev59.com/tEfRa4cB1Zd3GeqP83D8 - kajaco

3

不完全正确，这是两个队列而不是两个指针。 - paxdiablo

7

因为你在这里是来帮忙的，而不是为了玩一场声望游戏。 - GManNickG

1

你正在帮助那些从问题和答案中获益的读者，我发现这非常有见地。 - Andrew Coleson

1

双向链表可以在O(1)时间内实现反转。请查看我的答案。 - Karussell

显示剩余2条评论

36个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- deepak verma · Answer 1

是的，有一种方法只使用两个指针。那就是创建一个新的链表，其中第一个节点是给定列表的第一个节点，第一个列表的第二个节点添加到新列表的开头，以此类推。

- Jerry An · Answer 2

这是一个更简单的Python版本。它只使用了两个指针slow和fast。

def reverseList(head: ListNode) -> ListNode:

    slow = None
    fast = head
    while fast:  
        node_next = fast.next
        
        fast.next = slow
        slow = fast
            
        fast = node_next
    return slow

- Nikhil · Answer 3

您可以只使用一個額外指針來簡單地反轉連結列表。而實現這一點的關鍵是使用遞歸。

以下是Java程式碼。

public class Node {
   public int data;
   public Node next;
}

public Node reverseLinkedListRecursion(Node p) {
    if (p.next == null) {
        head = p;
        q = p;
        return q;
    } else {
        reverseLinkedListRecursion(p.next);
        p.next = null;
        q.next = p;
        q = p;
        return head;
    }
}

// call this function from your main method.
 reverseLinkedListRecursion(head);

正如您所看到的，这是一个简单的头递归示例。我们主要有两种不同类型的递归。

头递归：当递归是函数执行的第一件事时。
尾递归：当递归是函数执行的最后一件事时。

在这里，程序将继续递归调用自己，直到我们的指针“p”到达最后一个节点，然后在返回堆栈帧之前，我们将头指向最后一个节点，并将额外的指针“q”指向反向构建链表。

在这里，堆栈帧将继续返回，直到堆栈为空。

- Green goblin · Answer 4

你可以采用递归方法：

以下是伪代码：

Node* reverse(Node* root)
{
    if(!root) return NULL;

    if(!(root->next)) temp = root;
    else
    {
        reverse(root->next);
        root->next->next = root;
        root->next = NULL;
    }

    return temp;
}

在函数被调用后，它会返回链表的新根[temp]。因为很明显它只使用了两个指针。

- Vadakkumpadath · Answer 5

使用1个变量（仅限p）的解决方案：

typedef unsigned long AddressType;

#define A (*( AddressType* )&p )
#define B (*( AddressType* )&first->link->link )
#define C (*( AddressType* )&first->link )

/* Reversing linked list */
p = first;

while( first->link )
{
    A = A + B + C;
    B = A - B - C;
    A = A - B;
    C = A - C;
    A = A - C;
}

first = p;

- subhash konda · Answer 6

//with this no extra space and no extra scans but this code is reversing code but read
// in reverse direction no changes made in the linked list 
PrintInReverse(Node node)
{
   // given list is null
   if(node ==null)
       return null;
   // if list contains only one node
   if(node->next ==null)
   {
       print(node.value)
   }
   // call recursively 
   else
   {
       //while(node->next != null)// due to while loop it goes into infinite loop.use //if
       if(node->next!=NULL)
       {
           PrintInReverse(node->next)
           print(node.value)
       }
   }
}

Add comments...