Steven's Blog

A Dream Land of Peace!

Python倒置一个链表

We will show how to reverse a linked list in place using both python and javascript(actually converted from coffeescript).

1.python version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverse(head):
    p = head
    start = None
    while p:
        next_one = p.next
        p.next = start
        start = p
        p = next_one

    return start

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

result = reverse(head)
while result:
    print result.val
    result = result.next

2.javascript version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// Generated by CoffeeScript 1.9.3
var ListNode, head, result, reverse_linkedList;

ListNode = (function() {
  function ListNode(val) {
    this.val = val;
    this.next = null;
  }

  return ListNode;

})();

reverse_linkedList = function(head) {
  var next_one, p, start;
  p = head;
  start = null;
  while (p) {
    next_one = p.next;
    p.next = start;
    start = p;
    p = next_one;
  }
  return start;
};

head = new ListNode(1);

head.next = new ListNode(2);

head.next.next = new ListNode(3);

result = reverse_linkedList(head);

while (result) {
  console.log(result.val);
  result = result.next;
}

3.to reverse a linked from position m to n:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        dummyNode = ListNode(0)
        p = dummyNode
        q = head

        for x in range(m-1):
            p.next = q
            q = q.next
            p = p.next

        start = None
        end = q
        next_one = None

        for x in range(m, n+1):
            next_one = q.next
            q.next = start
            start = q
            q = next_one


        p.next = start
        end.next = next_one
        return dummyNode.next


if __name__ == '__main__':
    solution = Solution()

    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)

    m, n = 2, 4

    result = solution.reverseBetween(head, m, n)
    while result:
        print result.val
        result = result.next

4.we will also show another ways to reverse a linked list, first the cursive way:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverse(head):
    if head == None or head.next == None:
        return head

    second = head.next
    head.next = None
    result = reverse(second)
    second.next = head

    return result

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

result = reverse(head)
while result:
    print result.val
    result = result.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// Generated by CoffeeScript 1.9.3
var ListNode, head, result, reverse_linkedList;

ListNode = (function() {
  function ListNode(val) {
    this.val = val;
    this.next = null;
  }

  return ListNode;

})();

reverse_linkedList = function(head) {
  var result, second;
  if (head === null || head.next === null) {
    return head;
  }
  second = head.next;
  head.next = null;
  result = reverse_linkedList(second);
  second.next = head;
  return result;
};

head = new ListNode(1);

head.next = new ListNode(2);

head.next.next = new ListNode(3);

result = reverse_linkedList(head);

while (result) {
  console.log(result.val);
  result = result.next;
}