【leetcode刷题】T104-翻转链表

---

代码语言：javascript复制

【题目】翻转一个链表例如：
输入: 1->2->3->4->5->null
输出: 5->4->3->2->1->null
【思路】如果只使用两个指针p和q指向前后两个节点，当翻转时（q->next指向p），链表断了，无法继续。我们使用三个指针p、q、r，分别指向前后相邻的三个节点，进行交换时，首先改变r的指向：r = q->next；再翻转q->next = p；接着p和q后移，p = q, q = r。在最后，记得修改head->next以及head的指向。【代码】python版本# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 没有元素或者只有一个元素
        if not head or not head.next:
            return head
        p = head
        q = head.next
        r = p.next
        while q:
            r = q.next
            q.next = p
            p = q
            q = r
        head.next = None
        head = p
        return head
C  版本/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* p = head;
        ListNode* q = head->next;
        ListNode* r = q->next;
        while(q){
            r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        head->next = NULL;
        head = p;
        return head;
    }
};

leetcode

0 人点赞